堆排序（Heap Sort）
堆排序（HeapSort）是一树形选择排序。
堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录.
堆排序的时间复杂度是O(nlgn),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序而不是堆排序. 这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现. 堆排序的主要用途,是在形成和处理优先级队列方面. 另外, 如果计算要求是类优先级队列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同样是很适合的数据结构.
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1），
它是不稳定的排序方法。
如果需求是从很大的数据中选取特定的几个最大活最小值，那么堆排序是最好的选择。
堆排序的基本步骤就是：
1.初始建堆
2.将堆顶元素与有序区的第一个元素交换
3.然后对堆顶元素开始调整堆，跳转到2执行。直到全部有序。
该算法中最核心的算法是堆的调整算法
排序过程
最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点, 复杂度O(lgn)
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序, 复杂度O(n)
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算,复杂 度O(nlgn)
应用
常见的经典题目就是从10亿个数里面取最小的10个数(当然最大方法也一样,除了某些地 方反过来)
常见的错误(或者说不太合理)的方法是: 找最小的10个数,我就建一个最小堆 然后从堆里面min10次出来, 这个方法当然可行,但是这样一次要把所有的数据读入内存
最佳实现方法是:
在取最小的10个数的时候,用10亿个数的前十个建一个最大堆(不是写错了, 就是最大,同样取最大10个数的适合,建一个最小堆), 最大堆的堆顶肯定是这十个数 里面最大的一个了(也是最被嫌弃,最有可能被淘汰的一个)
然后用接下来的10亿个数,每次和这个最大堆堆顶进行对比, 比这个数还大的,就直接 抛弃, 比这个数小的话,就替代老的堆顶, 然后运行一次维护heap的操作,保持这个 最大堆的属性
最后剩下来的最大堆就说我们想要的前10个最小的.(前10个最大的反过来实现即可)