【数据结构初阶第十五节】堆的应用（堆排序 + Top-K问题）
必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-ZEEKLOG博客
对于本节我们要提前掌握前一节课堆的相关实现才能学好本次的知识，一定要多画图多敲代码看看实现的效果是啥（Crazy！）开始吧！
目录
——————————————《Being in love》——————————————
一、堆排序
（一） 基于原有堆
结合下面的代码观看——创建一个数组，将数组里面的数据不断地入堆后建立了一个堆（假设是一个小堆），不断取堆顶数据打印后出堆（此操作循环），这样就可以实现排序。为什么这样就实现了排序呢？Because小堆的堆顶是堆里面的最小值，出堆时向下调整又变成了小堆，此时堆顶是剩下元素里面的最小值，就这样不断取堆顶（最小值）实现了升序操作。
但是，这样的排序方法我们必须提前实现一个堆，而且我们实现堆操作时至少要申请一块原排序数组大小的空间，空间复杂度为O(N)，那该如何调整排序算法使空间复杂度变为O(1)呢？接下来看第二个排序方法
//1.需要堆的数据结构 //2，空间复杂度为O(N) void HeapSort(int* arr.int n) { HP hp; for (int i = 0; i < n; i++) { HPPush(&hp, arr[i]); } int i = 0; while(!HPEmpty(&hp)) { arr[i++] = HPTop(&hp)); HPPop(&hp); } HPDestroy(&hp); }（二） 原数组上直接建堆
1.向上调整算法建堆
原数组里建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据 。
void HeapSort(int* arr, int n) { //小堆->降序 //大堆->升序 for (int i = 0; i < 6; i++) { AdjustUp(arr, i); } //堆排序 int end = n - 1; while (end > 0) { Swap(&arr[0], &arr[end]);//end指向的是最后一个数据 AdjustDown(arr, 0, end);//有效的数据个数减了1 end--; } }上面是实现了排降序的操作，如何实现排升序的操作呢？异曲同工之妙！来看
上面建的是小堆，现在我们要在原数组内建大堆才能实现排升序的操作，如何建大堆呢？见下面的代码（要动手画图看看效果是如何实现建大堆的）
//向上调整数据，实现建堆操作 void AdjustUp(HPDatatype* arr, int child) { int parent = (child - 1) / 2; while (child > 0) { //建小堆，谁小谁往上放，用 < //建大堆，谁大谁往上放，用 > if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }//向下调整数据 void AdjustDown(HPDatatype* arr, int parent, int n) { int child = parent * 2 + 1; while (child < n) { //找出左右孩子中最小的->小堆 > //找出左右孩子中最大的->大堆 < if (child + 1 < n && arr[child] < arr[child + 1]) { child++; } // < 建小堆 // > 建大堆 if (arr[child] < arr[parent]) { Swap(&arr[parent], &arr[child]); parent = child; child = parent * 2 + 1; } else { break; } } }2.向上调整算法建堆时间复杂度
上面第二种方法我们实现的堆排序把空间复杂度降为O(1)，直接在原数组里面建堆不需要额外申请空间，那时间复杂度如何呢？
void HeapSort(int* arr, int n) { //小堆->降序 //大堆->升序 for (int i = 0; i < 6; i++) { AdjustUp(arr, i); } //堆排序 int end = n - 1; while (end > 0) { Swap(&arr[0], &arr[end]);//end指向的是最后一个数据 AdjustDown(arr, 0, end);//有效的数据个数减了1 end--; } }【大致估算】
结合排序代码思考，排序操作里面先是向上调整算法，假设堆的度为k，那么向上调整算法最差要向上交换k-1次；我们根据节点数来计算交换的次数，我们知道 2^k -1 = n（n为总结点的个数），k = log(n+1) -> k = log(n)，这只是插入一个结点，若要插入m个结点，就是m*log(n)次，因为向下调整算法也是这样，所以加起来就是O(2*m*log(n))，也就是O(m*log(n))，这只是大致计算一下时间复杂度。
【细致计算】
3.向下调整算法建堆
不仅仅可以向上调整算法建堆，还可以向下调整算法建堆。（根据代码原理自己动手画画图）
void HeapSort(int* arr, int n) { //向下调整算法建堆 for (int i = (n - 2) / 2; i >= 0; i--) { AdjustDown(arr, i, n); } //堆排序 int end = n - 1; while (end > 0) { //end指向的是最后一个数据 Swap(&arr[0], &arr[end]); //有效的数据个数减了1 AdjustDown(arr, 0, end); end--; } }4.向下调整算法建堆时间复杂度
感觉有点乱理一理先
实现堆排序 = 建堆 + 排序
如何建堆? 两种方法 --> 向上调整算法建堆 / 向下调整算法建堆
建大堆还是建小堆取决于你想排升序还是排降序，自行选择
建大堆 --> 升序
建小堆 --> 降序
二、TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，⼀般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能⼀下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
（1）用数据集合中前K个元素来建堆（自己好好想清楚）
- 取前K个最大的元素，则建小堆
- 取前K个最小的元素，则建大堆
（2）用剩余N-K个元素依次与堆顶数据来比较，不满足则替换堆顶元素
- 对于建小堆，若剩余元素比堆顶元素大则交换；
- 对于建大堆，若剩余元素比对顶元素小则交换。
时间复杂度为：我们采用向下调整算法建堆，时间复杂度为O(K)，之后将N-K个数据进行向下调整，时间复杂度为(N-K)log(K) ，加在一起将小影响的忽略就是O(N) 。 注意看自己AdjustDown实现的是大堆还是小堆。
void CreateNDate() { // 造数据 int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (int i = 0; i < n; ++i) { int x = (rand() + i) % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } void Top() { printf("请输入k："); int k = 0; scanf("%d", &k); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen error!"); return; } //申请一块堆大小的空间 int* minHeap = (int*)malloc(k * sizeof(int)); if (minHeap == NULL) { perror("malloc file!"); exit(2); } //将数据存入堆里面 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &minHeap[i]); } //建堆，通过向下调整算法建一个小堆 for (int i = (k - 2) / 2; i >= 0; i--) { AdjustDown(minHeap, i, 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); } int main() { CreateNDate(); Top(); return 0; }终于结束了！ （我要疯了真的）
完——
——————————————《Being in love》——————————————
Being in Love_Synth Monsters、川岛三离_高音质在线试听_Being in Love歌词|歌曲下载_酷狗音乐
[正是你对你的玫瑰花费的时光，才使你的玫瑰如此重要]
至此结束！
我是云边有个稻草人
期待与你的下一次相遇。。。
