数据结构之堆排序以及Top-k问题详细解析

个人主页：点我进入主页

专栏分类：C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶

C语言刷题数据结构初阶

欢迎大家点赞，评论，收藏。

一起努力

1.前言

2.堆排序

2.1降序排序

2.2时间复杂度

3.Top-k问题

4.总结

1.前言

在上一篇文章中我们主要讲解了关于大堆和小堆的代码实现，今天我们主要讲解关于堆排序以及堆排序的时间复杂度，我们会讲解关于经典的Top-k问题进行讲解（其中我会伪造一些数据来展示），今天的内容比上次的内容更加的爽，更有挑战性，其中的奥妙真的无法用语言来形容，接下来就让我们感受一下吧。

2.堆排序

我们对数组进行降序排序，我们使用堆排序，在这里由于升序和降序的思想基本一致，只需要修改一些符号即可完成转化，所以我们只讲关于降序的内容。

2.1降序排序

在上次的内容中我们使用向上调整来创建堆，我们是创建小堆还是大堆呢？我们想让数据进行降序，如果我们使用大堆的话堆的第一个数是最大的，我们取出来之后堆的顺序就乱了，我们需要重新进行大堆排序，那么我们的时间复杂度为O(n^2*logn),这比我们的冒泡排序还要慢，所以大堆是不可以的，所以我们选择小堆排序，我们这次依旧使用想上调整，详细代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
void Swap(int* num1, int* num2)
{int temp = *num1;*num1 = *num2;*num2 = temp;
}
void print(int* arr, int size)
{for (int i = 0; i < size; i++)printf("%d ", arr[i]);
}
void AdJustUp(int* arr, int sz,int size)
{assert(arr);int child = sz, parent = (child - 1) / 2;while (child>0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
void AdJustDown(int* arr, int i, int size)
{assert(arr);int parent = i, child = 2 * parent + 1;while (child<size){if (child + 1 < size && arr[child] >arr[child + 1]){child++;}if (arr[parent] > arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = 2 * parent + 1;}elsebreak;}
}
void HeapSort(int* arr, int n)
{assert(arr);for (int i = 0; i < n; i++){AdJustUp(arr, i, n);}for (int i = 0; i < n-1; i++){Swap(&arr[0], &arr[n - 1 - i]);AdJustDown(arr, 0, n - 1 - i);}}
int main()
{int arr[10];int n = 10;for (int i = 0; i < n; i++){arr[i] = i;}HeapSort(arr,n);print(arr, n);return 0;
}

我们的运行结构如下：

事实上我们这不是我们的堆排序，真正的堆排序在第一次创建小堆时代码为：

	for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdJustDown(arr, 0, n - 1 - i);}

向下调整为什么可以实现呢？，我们知道向下调整是左边和右边都是小堆然后根节点是新插入的我们就可以利用向下调整进行排序，那我们在最后一个节点的父节点进行向下调整，让他们都成为小堆，这样我们就可以完成小堆的创建。那为什么采用这种形式呢？仅仅是因为代码少吗？事实上这与我们的时间复杂度有关。

2.2时间复杂度

我们看利用向上调整建立小堆的时间复杂度，我们第k层有2^(k-1)个节点，每个节点需要向上调整k-1次共调整(k-1)*2^(k-1)次，第k-1层有2^(k-2)，每个节点需要调整k-2次，共调整(k-2)*2^(k-2)……第二层有2^1个节点，每个节点需要调整1次，第一层有2^0个节需要调整0次，共需要调整T(k)=0*2^0+1*2^1+……+(k-2)*2^(k-2)+(k-1)*2^(k-1),我们化简可以得到T(k)=(k-2)2^k+2;其中k=logN,所以T(k)=NlogN;但是我们采用向下调整我们第k层有我们第k层有2^(k-1)个节点，每个节点需要向上调整0次共调整0*2^(k-1)次，第k-1层有2^(k-2)，每个节点需要调整1次，共调整1*2^(k-2)……第二层有2^1个节点，每个节点需要调整k-2次，第一层有2^0个节需要调整k-1次,共需要调整T(k)=(k-1)*2^0+(k-2)*2^1+……+1*2^(k-2)+0*2^(k-1),我们化简得到T(k)=2^k-k-1，其中k=logN,故T(k)=N-logN;可以看到向下调整建立堆时间复杂度低，所以我们选择向下调整这大大减少了我们的运算时间。

3.Top-k问题

有一个问题是我们在一组数中(共N个数)找到最小的k个数，其中N远大于k，让我们找到前k个数，当数据很小的时候我们利用堆排序进行查找很容易，但是当数据量特别大的时候我们就很难实现，因为数据占用的内存太大了，例如我们要在1百亿个数据中找到前10个最小的数，100万个整形数据相当于占用37GB,这样我们就很难处理，这时候就出现了我们的Top-k问题，我们是如何解决这个问题呢？这时候我们由于需要找最小的前10个数据我们创建一个大堆，然后输入一个数据就将堆顶元素替换然后再向下调整这样就可以找到最小的10个数据，我们创建100万个数据进行模拟，我们的代码如下：

我们将数据放在文件中，生成data.txt文件

#include<stdio.h>
int main()
{FILE* pf = fopen("data.txt", "w");if (pf == NULL){perror("fopen fail");return 1;}for (int i = 0; i < 1000000; i++){fprintf(pf,"%d\n", i);}fclose(pf);pf = NULL;return 0;
}

修改其中的10个数据让他成为我们的结果，然后进行下一步找到这k个数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int MyHeapData;
typedef struct Heap {MyHeapData* data;int size;int capacity;
}Heap;
void HeapInit(Heap* php)
{assert(php);php->data = (MyHeapData*)malloc(sizeof(MyHeapData)*10);php->size = 0;
}
void Swap(int* num1, int* num2)
{int temp = *num1;*num1 = *num2;*num2 = temp;
}
void AdJustDown(int* arr, int n, int i)
{assert(arr);int parent = 0, child = 2 * parent + 1;while (child<n){if (child+1<n&&arr[child] < arr[child + 1]){child++;}if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
void AdJustUp(MyHeapData* arr, int size)
{assert(arr);int child = size - 1, parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
int main()
{//FILE* pf = fopen("data.txt", "w");//if (pf == NULL)//{//	perror("fopen fail");//	return 1;//}//for (int i = 0; i < 1000000; i++)//{//	fprintf(pf,"%d\n", i);//}//fclose(pf);//pf = NULL;FILE* pf = fopen("data.txt", "r");if (pf == NULL){perror("fopen fail");return 1;}int data;int i;Heap ph ;HeapInit(&ph);for (i = 0; i < 10; i++){fscanf(pf, "%d", &data);ph.data[i] = data;AdJustUp(ph.data, i);}while (fscanf(pf, "%d", &data) != EOF){if(data<ph.data[0])Swap(&data, &ph.data[0]);AdJustDown(ph.data, 10, 0);}for (i = 0; i < 10; i++){printf("%d ", ph.data[i]);}fclose(pf);pf = NULL;return 0;
}

运行结果如下：