2.4 优先队列

合适的数据结构支持两种操作：删除最大元素和插入元素

一 API

二 初级实现

2.1 数组实现（无序）

2.2 数组实现（有序）

2.3 链表表示法

三 堆的定义

四 堆的算法

打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。这个过程称为堆的有序化。

4.1 由下至上的堆有序化（上浮）

4.2 由上至下的堆有序化（下沉）

4.3 多叉堆

4.4 调整数组大小

4.5 元素的不可变性

4.6 索引优先队列

五 堆排序

堆排序分为两个阶段：在堆的构造阶段，将原始数组重新组织进一个堆中；

                                    在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结                                           果。

5.1 堆的构造

5.2 下沉排序

5.3 先下沉后上浮

堆排序是我们所知的唯一能够同时最优地利用空间和时间的方法----在最坏的情况下它也能够保证使用 ~ 2NlgN次比较和恒定的额外空间。

尽管如此，堆排序的应用仍然没有快速排序广泛和频繁，主要是因为：

1.堆排序的内循环比快速排序要复杂

   循环技术和各种需要注意的地方较快速排序多

2.堆排序不能有效利用缓存

   堆排序载入大数组时，数组的引用会很可能布满整个内存，而快速排序是递归调用，保留着很    多局部的引用，所以快速排序在利用缓存的效率上比堆排序高。

   现代机器的缓存命中率一般都会在 95% 以上，所以有效的利用缓存是很重要的。

   快排在递归进行部分的排序的时候，只会访问局部的数据，因此缓存能够更大概率的命中；而    堆排序的建堆过程是整个数组各个位置都访问到的，后面则是所有未排序数据各个位置都可能    访问到的，所以不利于缓存发挥作用。简答的说就是快排的存取模型的局部性（locality）更      强，堆排序差一些。

   速度和缓存的问题都反映了堆排序让数据过于大距离的移动，你观察某个元素在整个排序过程    中的移动过程，会发现它是前后大幅度的跑动；而快速排序则是尽快的移动到最终的位置，然    后做小范围的跳动。

3.同时和归并排序相比，堆排序是不稳定的，在开发一些要求排序稳定性的程序时，显然应该选    择归并排序