前言
在开始这一节的内容之前，我们先来回顾一下与堆相关的重点：
1、堆是二叉树顺序存储结构的一个具体体现，堆中每个节点的值总是不大于或不小于其父节点的值 (大堆/小堆)，堆总是一棵完全二叉树，堆使用顺序表存储元素；
2、堆中父节点下标的计算公式：(n-1)/2，左孩子下标：n*2+1，右孩子下标：n*2+2；
3、堆只能在尾部插入数据，且插入数据后需要保证堆的结构，所以在插入数据之后我们要进行向上调整，向上调整的时间复杂度为O(log N) (log 以2为底) ；
4、堆只能在头部删除数据，且删除数据后需要保证堆的结构，又因为顺序表头删需要挪动数据，效率很低，所以在堆删除数据会先将堆顶和堆尾的数据进行交换，然后让 size–，再进行向下调整，向下调整的时间复杂度为O(log N) (log 以2为底) 。
堆排序
堆排序是选择排序的一种，它的时间复杂度为 O(N*logN)，空间复杂度为 O(1)。
1、建堆
堆排序的第一步就是建堆，建堆有两种方法：向上调整建堆和向下调整建堆。
向上调整建堆： 把数组的第一个元素作为堆的根节点，然后在堆尾依次插入其余元素，每插入一个元素就向上调整一次，从而保证堆的结构；
向上调整建堆的时间复杂度： 由于堆是完全二叉树，而满二叉树是完全二叉树的一种，所以此处为了简化计算，使用满二叉树来得出时间复杂度 (时间复杂度本身看的就是近似值，多几个节点不影响最终结果)：
如上图，我们把每一次的节点个数除以每一个节点需要调整的次数，最后再求和，就可以得到一共需要调整的次数；然后再根据满二叉树节点总数与树的高度的关系将表达式中的h替换掉，最终可以得到向上调整建堆的时间复杂度为：O(N*logN)；
向下调整建堆： 从倒数第一个非叶子节点 (即最后一个叶节点的父节点) 开始向下调整，直到调整到根。
向下调整建堆的时间复杂度：
如上图，向下调整建堆的时间复杂度为：O(N)；
综合上面两种建堆方法，建堆的时间复杂度为：O(N)；
2、选数
现在我们建堆工作已经完成了，接下来就是选数，假设现在我们要排升序，那么方法一共有三种：
1、建小堆，开辟一个和原数组同等大小的新数组，每次取出堆顶的元素 (最小的元素) 放在新数组中，然后挪动数组中的数据，最后排好序以后再将新数组中的数据覆盖至原数组；
缺点：每次挪动数据的效率很低，且挪动数据会造成堆中其余元素父子关系混乱，需要重新建堆，而建堆的时间复杂度也是O(N)，所以二者嵌套后时间复杂度：O(N^2)，空间复杂度：O(N)；
2、也是建小堆，不过这次我们借鉴堆 pop 数据的方法，先将堆顶的元素放入新数组中，然后交换堆顶和堆尾的元素，之后再向下调整数组中前 n-1 个数据，直到排好序，最后将排好序以后再将新数组中的数据覆盖至原数组；
缺点：虽然此方法可以让我们每次都拿到数组中最小的元素，但是需要开辟额外的空间，时间复杂度：O(N*logN)，空间复杂度：O(N)；
3、建大堆，先将堆顶和堆尾的数据进行交换，使得数组中最大的元素处于数组末尾，然后向下调整前 n-1 个元素，使得次大的数据位于堆顶，最后重复前面的步骤，把次大的数据存放到最大的数据之前，直到数组有序；
优点：没有额外的空间消耗，且效率达到了 O(N*logN)；
综合上面三种选数的方法，选数的时间复杂度为：O(N*logN)，空间复杂度为：O(1)；
3、代码
//交换两个节点 void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向上调整 -- 大堆 void AdjustUp(int a[], int child) { int parent = (child - 1) / 2; //找出父节点 while (child > 0) //当调整到根节点时不再调整 { if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); } else { break; } //迭代 child = parent; parent = (child - 1) / 2; } } //向下调整 -- 大堆 void AdjustDown(int a[], int n, int parent) { int maxchild = parent * 2 + 1; //找到左孩子（左孩子+1得到右孩子） while (maxchild < n) //调整到数组尾时不再调整 { if (maxchild + 1 < n && a[maxchild + 1] > a[maxchild]) { maxchild += 1; } if (a[parent] < a[maxchild]) { Swap(&a[parent], &a[maxchild]); } else { break; } //迭代 parent = maxchild; maxchild = parent * 2 + 1; } } void HeapSort(int a[], int n) { //建堆 -- 向上调整建堆：O(N*logN) //int i = 1; //for (i = 1; i < n; i++) //{ // AdjustUp(a, i); //} //建堆 -- 向下调整建堆：O(N) for (int i = (n - 1 - 1) / 2; i >= 0; i--) //n-1找到最后一个叶节点，该节点-1/2找到倒数第一个父节点 { AdjustDown(a, n, i); } //排序 -- 升序（建大堆，向下调整）：O(N*logN) for (int i = n - 1; i > 0; i--) { Swap(&a[i], &a[0]); //交换堆尾和堆顶的元素 AdjustDown(a, i, 0); //向下调整 } } int main() { int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 }; int n = sizeof(a) / sizeof(a[0]); //堆排序 HeapSort(a, n); for (int i = 0; i < n; i++) { printf("%d ", a[i]); } return 0; }
TopK 问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大；比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是，如果数据量非常大，排序就不太可取了 (数据都不能一下子全部加载到内存中)，最佳的方式就是用堆来解决，基本思路如下：
第一步：用数据集合中前K个元素来建堆 – 前k个最大的元素，则建小堆；前k个最小的元素，则建大堆；
第二步：用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素；
//交换两个节点 void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下调整 -- 小堆 void AdjustDown(int a[], int n, int parent) { int minchild = parent * 2 + 1; //找到左孩子（左孩子+1得到右孩子） while (minchild < n) //调整到数组尾时不再调整 { if (minchild + 1 < n && a[minchild + 1] < a[minchild]) { minchild += 1; } if (a[parent] > a[minchild]) { Swap(&a[parent], &a[minchild]); } else { break; } //迭代 parent = minchild; minchild = parent * 2 + 1; } } int* TopK(int a[], int n, int k) { //开辟K个元素的空间 int* minHeap = (int*)malloc(sizeof(int) * k); if (minHeap == NULL) { perror("malloc fail"); return NULL; } //将数组前K个元素拷贝到新空间 for (int i = 0; i < k; i++) { minHeap[i] = a[i]; } //建小堆 -- 向下调整建堆：O(N) for (int i = (k - 1 - 1) / 2; i >= 0; i--) //n-1找到最后一个叶节点，该节点-1/2找到倒数第一个父节点 { AdjustDown(minHeap, k, i); } //取后N-k个元素与堆顶元素比较，如果大于堆顶元素，就入堆 for (int i = k; i < n; i++) { if (minHeap[0] < a[i]) { minHeap[0] = a[i]; AdjustDown(minHeap, k, 0); } } return minHeap; } int main() { int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 }; int n = sizeof(a) / sizeof(a[0]); //TopK问题 -- 前K个最大的元素 int k = 3; int* ret = TopK(a, n, k); for (int i = 0; i < k; i++) { printf("%d ", ret[i]); } free(ret); ret = NULL; return 0; }
