优先队列（堆）

二叉堆

基本性质

结构性
其逻辑结构是一个完全二叉树。
由于完全二叉树十分有规律，所以可以用一个数组表示，而不需要用链表。
对于数组中任一位置 $i$ 上的元素，其左儿子在 $2i$ 上，右儿子在 $2i+1$ 上，它的父元素则再 $\left\lfloor i/2 \right\rfloor$
堆序性
在一个堆中，对于每一个节点X，X的父亲中的关键字小于或等于X中的关键字（根节点除外）

基本操作

插入(insert)
在插入时，我们在下一个可用位置（即完全二叉树最底端的下一个空余位置）建立一个空穴，然后将待插入的元素与该空穴的父节点元素进行比较，如果父节点小，则将待插入的元素放入空穴中，否则，将父节点元素放入空穴，并将父节点中元素置空(变为空穴，即上滤)，继续进行上述操作，直至插入完成或者到达根节点。
查找最小元(findMin)
根据堆序性，直接返回根节点元素
删除最小元(deleteMin)
在根节点建立一个空穴，选择空穴的子节点中元素较小的节点移入空穴，这样就相当于把空穴下滤了，重复上述操作，直到无法下滤为止
合并(merge)
将原堆数组扩大，然后通过 N 次 insert 操作将要合并的另一个堆中的元素合并到原堆当中。

其他操作

降低关键字的值(decreaseKey)
在降低了关键字的值后，通过上滤来重新构建堆
提升关键字的值(increaseKey)
在提升了关键字的值后，通过下滤来重新构建堆
删除(delete)
先通过decreaseKey(p,$\infty$)来使被删除的元素位于堆的最上方，然后在通过deleteMin()来删除该元素。
构建堆(buildHeap)
通过N次 insert 操作构建含有 N 个元素的堆。

二叉堆总结

注意点
在堆的实现过程中，经常发生的错误是当堆中存在偶数个元素的时候，将遇到一个节点只有一个儿子的情况。因此我们必须保证节点不总有两个儿子的前提。处理这个前提有以下两种方法
- 添加一个额外的判定，来辨别是否有右儿子，即是否有两个儿子
- 当堆中元素为偶数个时，在下滤开始时，将一个 $\infty$ 大的元素插入到该堆的最后一个位置，这样我们每个节点都可以看做有两个儿子来对待（任需测试何时到达底层）
优点
- 可以通过数组实现，实现起来简单
- 由于是由数组实现的，其各项操作运行效率将变高。
缺点
- 不能实施find
- 合并时，需要把一个数组拷贝到另一个数组中去，对于相同大小的堆，这将花费时间 $\theta(N)$
  
  正因为上述的第二个缺点，所有支持有效合并的高级数据结构都需要使用链式数据结构，也就是以下的左式堆、斜堆、二项队列。

左式堆

基本性质

结构性
对于堆中的每一个节点X，左儿子的零路径长>=右儿子的零路径长
ps: 零路径长(npl)指的是从节点X到一个不具有两个儿子的节点的最短路径长，其中 $npl(null) = -1$
堆序性
在一个堆中，对于每一个节点X，X的父亲中的关键字小于或等于X中的关键字（根节点除外
其他性质
- 在右路径上有 r 个节点的左式树必然至少有 $2^r-1$ 个节点
- 任一节点的零路径长比它的儿子节点的零路径长的最小值大1

基本操作

插入(insert)
同合并操作，只不过此时合并的堆只含有一个节点。
查找最小元(findMin)
根据堆序性，直接返回根节点元素
删除最小元(deleteMin)
删除根节点，得到两个堆（即左右儿子），然后再合并两个堆得到新的堆
合并(merge)
自上而下递归，比较两个堆根节点元素大小，将根节点大的堆与根节点小的堆的右儿子合并，并更新零路径长。若此时右儿子的零路径长大于左儿子的零路径长(即破坏了左式堆的结构性)，则交换左右儿子，直到到达叶子结点。

其他操作

构建堆(buildHeap)
可以通过递归地建立左右子树，然后将跟下滤来得到

斜堆

基本性质

堆序性
在一个堆中，对于每一个节点X，X的父亲中的关键字小于或等于X中的关键字（根节点除外）

基本操作

插入(insert)
同合并操作，只不过此时合并的堆只含有一个节点。
查找最小元(findMin)
根据堆序性，直接返回根节点元素
删除最小元(deleteMin)
删除根节点，得到两个堆（即左右儿子），然后再合并两个堆得到新的堆
合并(merge)
自上而下递归，比较两个堆根节点元素大小，将根节点大的堆与根节点小的堆的右儿子合并，交换左右儿子（这里是与左式堆不同的地方，左式堆需要进行一次判定，而斜堆除去右路径上最后的节点外其他所有节点的左右儿子都直接交换），直到到达叶子结点。

其他操作

构建堆(buildHeap)
可以通过递归地建立左右子树，然后将跟下滤来得到

斜堆总结

优点
相比于左式堆，斜堆不需要附加的空间来保留零路径长以及不需要测试已确定何时交换儿子

二项队列

基本性质

结构性
二项队列是堆序的树的集合，称为森林。每一棵堆序树都是有约束的形式，叫做二项树。每一个高度上至多存在一棵二项数。高度为0的二项树是一棵单节点树；高度为K的二项树$B_k$通过将一颗高度为$k-1$的二项树$B_{k-1}$附接到另一棵二项树$B_{k-1}$的根上而构成。
一个二项队列如下图所示
堆序性
在一个堆中，对于每一个节点X，X的父亲中的关键字小于或等于X中的关键字（根节点除外）
其他性质
- 高度为k的二项树含有$2^k$个节点
- 高度为k的二项树,在深度d处的节点数是二项系数${k \choose d}$

基本操作

插入(insert)
参考合并操作，只不过现在合并的就是高度为0的二项树
查找最小元(findMin)
有两种方法
- 当数据结构中专门有一个域用来保存最小元信息时，直接返回该最小元，这时需要$O(1)$的运行时间
- 当数据结构中没有这样一个域时，则需要比较该二项队列中所有二项树的根节点的信息，选择最小的返回
删除最小元(deleteMin)
查找最小元所在的二项树$B_K$，删除它的根节点，这时会产生一个二项队列{$B_0,B_1,B_2….B_{K-1}$},然后再将该二项队列，与删除该二项树后剩下的二项队列合并，得到新的二项队列，如果数据结构中有专门的域来存放最小元信息，则更新该域。
合并(merge)
将两个二项队列中所有的二项树进行合并
- 当高度为K的二项树$B_{k}$存在两个及以上的时候（即由两棵高度为k-1的二项树合并而来的新二项树，再加上原有的高度为K的二项树，就有可能出现同时存在三棵高度相同的树二项树的情况），这时合并其中的两棵二项树，形成新的二项树$B_{k+1}$
- 当高度为K的二项树$B_{k}$只有一个的时候，则保持不变
- 合并时将根节点较大的二项树附加到根节点较小的二项树上，即根节点较大的节点成为根节点较小的节点的子节点

其他操作

构建堆(buildHeap)
可以通过多次使用Insert来完成

二项队列的实现

每个节点都将包含数据、第一个儿子的引用以及右兄弟的引用
二项树中的各个儿子按降序排列
所有二项树的根节点按该二项树的高度，从小到大存储在一个数组中

堆的实际应用

选择问题
事件模拟

几种堆的基本操作平均运行时间比较

	二叉堆	左式堆	斜堆	二项队列
插入（insert）	$O(\log N)$	$O(\log N)$	$O(\log N)$	$O(1)$
查找最小元（findMin）	$O(1)$	$O(1)$	$O(1)$	$O(1)$
删除最小元（deleteMin）	$O(\log N)$	$O(\log N)$	$O(\log N)$	$O(\log N)$
合并（merge）	$O(N)$	$O(\log N)$	$O(\log N)$	$O(\log N)$