之前我们实现的堆是创建一个数组，将元素组的内容拷贝过来进行排序的，这样的空间复杂度是O(N)，我们可对堆进行优化，使得不拷贝元素，直接在原数组上进行操作使得原数组变为有序的数组
堆的建立
向上调整建堆
//建堆——向上调整建堆 第一个元素看作一个堆，后面的元素看作依次插入 for (int i = 1; i < n; ++i) { AdjustUp(a, i); }
向下调整建堆
之前向下调整的建堆方法是，头尾交换然后将头向下调整，向下调整的前提是左右子树都是大堆或小堆
当数组是这个样子。就无法使用向下调整
我们可以从倒数第一个非叶子节点（倒数第一个叶子节点的父节点）开始向下开始调，直到调整到根，叶子节点没必要调（兄弟关系），
先让i指向60，然后60和70交换，i--，i指向100再进行调整，之后再i--，i等于100进行调整
//建堆——向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点 //物理上操作数组，逻辑上在操作堆 { AdjusuDown(a, n, i); }
向上调整和向下调整时间复杂度的比较
向下调整时间复杂度：O（N）
向下调整总步数=该层个数*需向下调整次数
当满二叉树节点较多时，最后一层节点的个数约为总结点个数的一半，向下调整的好处：节点所在层数越小（以第1层为比较基准），调整次数越多，节点所在层数越大，此时节点越多，调整次数越小
向上调整时间复杂度：O(N*logN)
利用错位相减可计算出调整次数
我们只算最后一层的调整次数
向上调整：越往下节点越多，调整次数越多，算法时间复杂度过大
大小堆如何选择
对于升序和降序我们该如何选择建堆方式？
答案：1.升序——大堆 2.降序——小堆
大思路：选择排序，依次选数，从后往前排
升序建小堆会出问题
建堆的时间复杂度是O(N)，效率低
选数
//选数 int i = 0; while (i < n) { Swap(&a[0], &a[n - i]); AdjusuDown(a, n - i, 0); ++i; }
void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent) { HPDataTypedef minChild = parent * 2 + 1; while (minChild<n) { if (minChild+1<n&&a[minChild+1] >a[minChild]) { minChild++; } if (a[minChild] > a[parent]) { Swap(&a[parent], &a[minChild]); parent = minChild; minChild = parent * 2 + 1; } else break; } } void Heapsort(int* a, int n) { //建堆——向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点 //物理上操作数组，逻辑上在操作堆 { AdjusuDown(a, n, i); } //选数 int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjusuDown(a, n - i, 0); ++i; } } int main() { int a[] = { 65,100,75,32,50,60 }; Heapsort(a, 6); return 0; }
Top-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
找前K个最大的
1.排序——O(N*logN)
2.堆选数
a.建大堆和建小堆都可以，建大堆相当于选K次（Pop k次）时间复杂度：O(N+logN*k)
