本章讨论优先队列（priority queue），介绍优先队列在离散事件模拟中的应用
作者评价：这类数据结构属于计算机科学中最雅致的一种
内容
- 优先队列ADT的高效实现
- 优先队列的使用
- 优先队列的高级实现
二叉堆 (binary heap)
插入删除最坏O(logN)，实际上插入花费常数平均时间，若无删除干扰，该结构将以线性时间建立一个具有N项的优先队列。
与二叉查找树一样，堆具有两个性质，堆的操作必须满足所有性质才能终止。
结构性质
堆是一棵完全二叉树（三角形缺右下角），特例是满二叉树（三角形），最底层元素必须从左往右填入，如有空缺则不是完全二叉树
一棵高为h的完全二叉树有[2^h , 2^(h+1) - 1]个节点，这意味着完全二叉树的高是 下取整(logN)，显然它是O(logN)的
因为此规律，所以堆可以用数组表示而不用链表，对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的(2i+1)上，它的父亲在位置 下取整(i/2) 上
堆序性质
在堆中，除根节点以外，每一个节点的值都大于（或等于）它的父节点的值
根据堆序性质，最小值总在根结点，因此可以以O(1)时间做findMin
相应地，通过改变堆序性质，也可以建立一个max堆，以O(1)时间做findMax
插入（上滤策略）
为了插入新元素X，在堆的下一个可用位置（为了满足结构性质）创建一个空穴，若X放入空穴仍满足堆序性质，则插入完成，否则交换空穴和其父节点，直到X被放入并满足堆序性质为止
删除（下滤策略）
找出最小元很容易，难的是删除它。
当删除一个最小元时，堆中最后一个元素X必须移动到该堆的某个地方。策略是在根节点建立一个空穴，然后将两个儿子中的较小者移入空穴，重复该步骤直到X可以被放入空穴中。代码中则是用X直接替换根结点的值，然后下滤。
注意
在堆的实现中经常出现的错误是，当堆中存在偶数个元素时，将出现一个节点只有一个儿子的情况。因此我们必须以节点不总有两个儿子为前提，这需要额外的测试。
应用
选择问题
输入N个元素及整数k，找出第k个最大的元素，极端情况是k=上取整(N/2)，此时实际上是找中位数，以下两个算法都能在找中位数的情况下以O(NlogN)时间运行
- A 将N个元素读入数组，对数组应用buildHeap，再执行k次deleteMin，最后根节点上的就是第k个最小值，构造一个最大堆就可以找到第k个最大值
- B 用buildHeap将前k个元素构造成一个最大堆，若下一个元素大于堆里的最小值，则删除最小值，插入新元素，最终的最小值就是所求的第k个最大值
d堆
类似B树，深度变浅，每个节点有d个儿子
左式堆 (leftist heap)
左式堆也是二叉树，但它不是理想平衡的，事实上是趋于非常不平衡
定义任一节点X的**零路径长(null path length)**npl(X)为从X到一个不具有两个儿子的节点的最短路径长
因此，具有0个或1个儿子的节点npl为0，而npl(NULL)=-1
注意，任一节点的npl比它儿子节点的npl的最小值多1
左式堆性质
对于堆中的每一个节点X，左儿子的npl至少与右儿子的npl一样大
这个性质导致树向左增加深度，沿左式堆右侧的右路径是堆中最短的路径
定理：在右路径上有r个节点的左式堆必然至少有2^r -1个节点
对左式堆的基本操作是合并。插入可以看成是合并一个单节点堆，删除即是删掉根结点，然后合并左右子树。
斜堆 (skew heap)
斜堆是左式堆的自调节形式，具有堆序，但不存在结构限制。斜堆不需要存储npl，每次合并无条件交换左右儿子。
二项队列 (binomial queue)
以最坏O(logN)支持插入、合并、deleteMin，插入操作平均花费常数时间
实质是由二项树(binomial tree)构成的森林(forest)。
每一个高度上最多存在一棵二项树。高度为k的二项树Bk是通过将一棵二项树B(k-1)附接到另一棵二项树B(k-1)的根上构成的。高度为k的二项树有2^k个节点，在深度d处的节点数是二项系数C(d,k)
如果把堆序性质施加到二项树上并允许任意高度上最多一棵二项树，则可以用二项树的集合唯一地表示任意大小的优先队列。如大小为13的优先队列可以用B3,B2,B0表示，可以写成1101，同时也是13的二进制形式。
操作
基本操作仍然是合并，思想是从小到大合并相同高度的二项树
插入是特殊情况下的合并
deleteMin将原二项队列一分为二，再合并
编程需要注意进位的实现