【完全二叉树魔法：顺序结构实现堆的奇象】（中）： https://developer.aliyun.com/article/1424933
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此：建堆的时间复杂度为O(N)。
6.堆排序
1. 排序如何建堆
- 升序：建大堆
- 降序：建小堆
为什么升序是建大堆呢？按照我们的常理，我们先建小堆，然后再取出堆顶的数据，这样就取得了最小的数据，这样数据不就有序了，为什么要去建大堆呢？？？
取出堆顶的数据，这样就取得了最小的数据，然后再选次小的数，此时我们只能将剩下的数看做堆，但是剩下的数据还是堆嘛？
此时就要重新建堆，然后再取堆顶数据，再建堆...每次建堆的时间复杂度N*logN，一共有N个数据，所以总的排序时间复杂度就是N * logN * N，那还不如直接遍历一遍排序来的快呢！！！
2. 利用堆删除思想来进行排序
所以此时我们可以建大堆，将堆顶的数据和最后一个叶子结点交换，由于此时的堆结构没有破坏，左子树和右子树仍然是堆，使用堆的向下调整去调整堆，然后在缩小下次向下调整的范围，也就是把最大的那个数不算做堆的范围了，这样最大的数据就保存在了下标最大的位置处，满足了升序的要求。每次向下调整的时间复杂度是logN，一共有N个数据，所以总的排序时间复杂度就是N * logN。
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> void Swap(int* p1, int* p2) { int temp = *p1; *p1 = *p2; *p2 = temp; } //向上调整 void AdjustUp(int* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //向下调整 void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; //parent到叶子结点就结束 while (child < n) { //可能不存在右孩子 if (child + 1 < n && a[child] < a[child + 1]) { child++; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort1(int a[],int n) { //建堆 //向上调整：前提是前面的数据是堆 // 思路：第一个数据当作堆，后面数据依次插入，向上调整 //O(N*logN) for (int i = 1; i < n; i++) { AdjustUp(a, i); } //升序建大堆 //O(N*logN) //向下调整：前提是左右子树是堆 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } } void HeapSort2(int a[],int n) { //建堆 //向下调整：前提是左右子树是堆 // 思路：找到倒数第一个非叶子结点，与最后一个叶子结点进行向下调整，直至根节点 //O(N) for (int i = (n - 1 - 1)/2; i >= 0; i--) { AdjustDown(a, n, i); } //升序建大堆 //O(N*logN) //向下调整：前提是左右子树是堆 int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } } int main() { int a[] = { 3,17,4,20,16,5 }; //HeapSort1(a,sizeof(a)/sizeof(a[0])); HeapSort2(a,sizeof(a)/sizeof(a[0])); int i = 0; for (i = 0; i < sizeof(a) / sizeof(a[0]); i++) { printf("%d ", a[i]); } return 0; }
运行结果：
7.TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
这里不能用大堆，如果第一个数据就是最大的，放在堆顶，其余数据就无法入堆，所以要用小堆，最大的前k个数肯定比堆顶大，此时该数替换堆顶的数入堆，入完k个后就找到前k个最大的元素。
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
3.复杂度
时间复杂度：O(N*logK)
空间复杂度：O(K）
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> void Swap(int* p1, int* p2) { int temp = *p1; *p1 = *p2; *p2 = temp; } //向下调整 void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; //parent到叶子结点就结束 while (child < n) { //可能不存在右孩子 if (child + 1 < n && a[child] > a[child + 1]) { child++; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void PrintTopK(const char *filename, int k) { // 1. 建堆--用a中前k个元素建堆 FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fopen fail"); exit(-1); } int *Minheap = (int*)malloc(sizeof(int) * k); if (Minheap == NULL) { perror("malloc fail"); exit(-1); } //读文件 for (int i = 0; i < k; i++) { fscanf(fout, "%d", &Minheap[i]); } //向下调整建小堆 for (int i = (k-2)/2; i >= 0; --i) { AdjustDown(Minheap, k, i); } // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 int x = 0; while (fscanf(fout, "%d", &x) != EOF) { if (x > Minheap[0]) { Minheap[0] = x; AdjustDown(Minheap, k, 0); } } for (int i = 0; i < k; ++i) { printf("%d ", Minheap[i]); } printf("\n"); fclose(fout); } void CreatNData() { //造数据 int n = 10000; srand((unsigned int)time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen fail"); exit(-1); } for (int i = 0; i < n; ++i) { int x = rand() % 1000000; fprintf(fin, "%d\n", x); } fclose(fin); } int main() { //CreatNData(); PrintTopK("data.txt",10); return 0; }
运行结果：
但是我们怎么知道这几个数据就是前k个最大的呢？我们可以在文件中手动创造10个最大的值，看看输出是不是我们刚刚手动创造10个最大的值。
1000001;1000002;1000003;10000041000005;
1000006;1000007;1000008;1000009;1000009。
这样就完成了我们的TOP-K问题！！！
