堆的应用——堆排序和TOP-K问题

1.堆排序

想法⼀：

基于已有数组建堆、取堆顶元素完成排序。也就是利用写好的堆数据结构（之前的文章有讲解），去实现排序。

void HeapSort(int* a, int n){HP hp;for(int i = 0; i < n; i++){HPPush(&hp,a[i]);}int i = 0;while (!HPEmpty(&hp)){a[i++] = HPTop(&hp);HPPop(&hp);}HPDestroy(&hp);

先依次入堆，然后再将堆顶，数据依次取出，为大堆即是降序，小堆为升序。实际上这种方法使用起来是很不方便的，必须要有堆的数据结构，而且时间复杂度为O（n）。

想法⼆：

数组建堆，⾸尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次⼤的数据。

void HeapSort(int* arr, int n)
{//根据给定的arr来进行建堆//child:n-1  parent:(n-1-1)/2向下调整算法建堆//for (int i = (n - 1 - 1) / 2; i >= 0; i--)//O(n)//{//	AdjustDown(arr, i, n);//O(logn)//}//向上调整建堆for (int i = 0; i < n; i++){AdjustUp(arr, i);}//堆排序//排升序---建大堆//排降序---建小堆int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}}

这里利用的是堆的思想，而不是直接用堆来排序，首先要建堆，将传进来的数组入堆，这里以建小堆为例，利用向下调整的方法，将一个个依次调整直到，直到根节点；

这里完成了建堆，那后面接下来，排序怎么办，其实利用思想将堆顶元素，与最后一个元素交换，再将元素个数减一，将剩余的堆进行调整，依次交换直到到堆顶。最后发现建的小堆，其实是降序排列，反之降序是建小堆。

这样就排序完成。

注意：这里考虑一个问题，向上调整可以建堆，向下调整也可以建堆，那个时间复杂度更低。

1.2向上调整算法和向下调整算法比较：

向上调整算法：

往下结点个数逐渐增多，向下调整次数增多；

可以推出向上调整建堆时间的复杂度：O(n*logn)；

向下调整算法：

可以推出向下调整建堆时间的复杂度：O（n）；

比较发现向下调整算法更优。

2.TOP-K问题

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。 ⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：

第一步：⽤数据集合中前K个元素来建堆

（这和前面堆排序有一些相似）

前k个最⼤的元素，则建⼩堆；

前k个最小的元素，则建⼤堆；

第二步：⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素

将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素

void TopK()
{int k = 0;printf("请输入K：");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最大的前K个数，建小堆int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//读取文件中前K个数据建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minHeap, i, k);}//遍历剩下的n-k个数据，跟堆顶比较，谁大谁入堆//调整堆int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minHeap[0]){minHeap[0] = x;AdjustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);
}

这里一些文件操作函数，可以看看小编前面的文章有讲解。