二叉堆
二叉堆是一棵完全二叉树，且任意一个结点的键值总是小于或等于其子结点的键值（最小堆）。
二叉堆采用数组来存储（按广度优先遍历的顺序），而没有像普通的树结构使用指针来表示节点间的关系。
堆示意图.jpg
- 最大堆：父结点的键值总是大于或等于任何一个子结点的键值；最大堆常用于排序算法。
- 最小堆：父结点的键值总是小于或等于任何一个子结点的键值；最小堆常用于优先队列。
堆的意义就在于：最快的找到最大/最小值，在堆结构中插入一个值重新构造堆结构，取走最大/最下值后重新构造堆结构；其时间复杂度为O(logN)；
堆排序
所谓堆排序，就是先建立N个元素的二叉堆，花费O(N)时间，然后执行N次deleteMax操作，每个deleteMax花费O(logN)时间，因此总的运行时间是O(NlogN)。
为了节约空间，每次deleteMax之后，堆缩小了1，所以可以用堆中最后的单元来存放刚刚删去的元素，这样不需要额外空间。
下面是《数据结构与算法分析：C++描述》（第3版）199页堆排序代码
template <typename Comparable>
void heapsort(vector<Comparable> & a){
//建堆，只需要从size的一半开始下滤就够了
for (int i = a.size() / 2; i >= 0;--i)
percDown(a, i, a.size());
for (int j = a.size() - 1; j > 0;j--){
swap(a[0], a[j]);
percDown(a, 0, j);
}
}
//返回堆中第i个元素的左儿子，注意这里堆数组从0开始
inline int leftChild(int i){
return 2 * i + 1;
}
//i是需要下滤的节点，n是堆的大小
template <typename Comparable>
void percDown(vector<Comparable> &a, int i, int n){
Comparable temp;
int child;
//先把要下滤的值a[i]存在temp里
for (temp = a[i]; leftChild(i)< n;i = child){ //终止条件，左儿子超出堆大小
child = leftChild(i); //找到左儿子节点
//如果右儿子存在且比左儿子大，选择右儿子
if(child != n-1&& a[child+1]>a[child])
child++;
if(temp < a[child]) //儿子比老子大，儿子上位
a[i] = a[child];
else //儿子比老子小，那么找到下滤值该放的位置了
break;
}
a[i] = temp; //把下滤值放到a[i]
}
最后放上大佬总结的heapsort.cpp
ClassicalCode:heapSort.cpp
求前K大（小）的数
利用最小堆和最大堆可以求一个包含N个元素的数组的前K大（或小）的数，原理如下：
我们首先取这N个元素中的前K个元素来建立一个由K个元素组成的小（大）顶堆，这样堆顶元素便是当前已读取元素中的第K大（小）者；然后，依次读取剩下的N-K个元素，而对于其中的每个元素x，若x大于（小于）当前的堆顶元素，则将堆顶元素替换为x，并自堆顶至向下调整堆；这样，在读取完所有元素后，堆中的K个元素即为这N个数中的前K个最大（小）元素，同时堆顶元素为这N个数中的第K大（小）元素。
