优先队列

一、什么是优先队列？

在实际应用中，以打印机为例，有的作业虽然排在后面，但很重要，需要优先打印，这种带有优先级的队列，叫做优先队列（priority queue）。
优先队列是允许至少下面两种操作的数据结构：

• insert（插入）
• deleteMin（删除最小者）：找出、返回并删除优先队列中最小的元素。

优先队列的应用场景：操作系统、外部排序算法、贪婪算法……

二、优先队列的一些简单实现思路

• 思路一：使用链表，在表头以O(1)执行插入，删除时，先查找到最小值，然后删除，这需要O(N)时间。
• 思路二：使用链表，让链表始终处于排序状态，插入需要O(N)时间，删除最小则只需要O(1)时间。
• 思路三：使用二叉查找树。它对这两种操作的平均运行时间都是O(logn)。

三、二叉堆(binary heap)

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构，所以堆也叫做二叉堆。

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

二叉堆满足二个特性：

1. 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2. 每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于 任何一个子节点的键值时为最小堆。
堆有两个性质：结构性和堆序性。

结构性质：

完全二叉树的性质：一颗高为h的完全二叉树有2^h到2^h+1-1个节点。这意味着完全二叉树的高是logN的向下取整，因此它是O(logN)的。
因为完全二叉树的严格规律性，所以可以用一个数组而不是链表来表示它。
对于数组中任一位置i上的元素，其左儿子在位置2i上，有儿子在左儿子后的单元（2i+1）中，他的父亲则在位置i/2向下取整的位置上。

堆序性质：

让操作快速执行的性质是堆序性质(heap-order property).由于我们想要找到最小的元素，那么为了更快得到，我们让最小元素始终位于堆顶。这就得到了堆序性质：
在一个堆中，对于每一个节点X，它的父亲节点的值小于它的值，根节点除外。
堆是一颗完全二叉树，但是由数组实现。

堆的基本操作

insert（插入）

使用上滤(percolate up)：在下一个可用位置创建一个空穴（保证该树是完全而插入），如果X可以放在该空穴中而不破坏堆的序，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中。这样，空穴就朝着跟的方向冒一步。继续该过程直到X能被放入空穴中为止。图解过程：

代码实现：
先空着，后面自己实现

deleteMin删除最小元

找到最小值是简单的，困难在于删除。
实现思路是：在最小堆中，最小值是跟，要删除最小值时，我们将根设为空穴。然后将根的两个儿子中较小的上移入空穴，这样就把空穴向下推了一层。重复该步骤直到X可以被放入空穴中。
一个需要注意的问题是，如果堆中存在偶数个元素，将遇到一个节点只有一个儿子的情况。解决的方法是：当堆的大小为偶数时在每一个下滤开始处，可将其值大于堆中任何元素的标记放到堆的终端后面的位置上。
这种操作的最坏情形运行时间为O(logN).

四、优先队列的应用

选择问题

问题描述：输入N个元素以及一个整数k，找出这N个元素中第K个最大元素。
解决思路：

算法1A（全排序）：

把这些元素读入数组并排序，返回适当的元素。不足：假设使用的是简单排序算法，则运行时间是O(N²)。

算法1B（K排序）：

将k个元素读入一个数组并将它们排序，接着一个一个读入其他元素，若读入的元素大于第K个元素（排序后最小），则将第K个元素删除，并将读入的元素插入适当的位置。当算法结束时，第K个位置上的元素就是问题的解答。该方法的运行时间为O(N*k)，因对K个数排序需要N²，剩余N-k个数最坏情况下都在数组头部插入，需要(N-k)*k，则N²+(N-k)*k=N*k。
不足：如果k=N/2，那么这两种算法都是O(N²)。对于任意的k，我们可以求解对称的问题：找出第(N-k+1)个最小的元素，从而，k=N/2实际上是这个算法的最困难的情况。
下面两个算法在k=N/2的极端情形下，均以O(NlogN)运行，这是明显的改进。

算法6A

我们将N个元素读入一个数组，然后对该数组应用buildHeap算法构造一个大根堆。最后，执行k次deleteMax操作，则最后返回的元素就是我们需要的答案。
运行时间分析：使用buildHeap构造堆的最坏情形用时O(N)，而每次deleteMax用时O(logN)。由于有k次deleteMax，因此我们的得到总的运行时间为O(N+k*logN)。当k=N/2时，运行时间为θ(NlogN)。

算法6B

我们采用算法1B的思路。调用buildHeap将k个元素构造成一个堆，运行时间为O(k)。其余N-k个元素一次与堆中最小元素（根）进行比较，如果大，则移除根，并将该元素放到堆中合适的位置，该过程用时O((N-k)*logk)。故总的时间为O(k+(N-k)*logk)=O(Nlogk)。该算法也给出找出中位数的时间界为θ(NlogN)。

五、d-堆

d-堆是二叉堆的简单推广，它就像一个二叉堆，只是所有的节点都有d个儿子（一次，二叉堆是2-堆）。
d-堆比二叉堆要浅的多，它将insert操作的运行时间改进为O(log_dN)。然而，对于大的d，deleteMin操作费时得多，因而树的变多了，那么找出儿子中的最小值需要的比较次数也增加了，如果使用标准算法，这会花费d-1次比较，于是将操作的用时增加到O(dlog_dN)。
当优先队列太大而不能完全装入主存的时候，d-堆很有。
除了不能进行find操作外，堆实现的最明显的缺点是：将两个堆合并成一个堆是困难的。这种附加操作叫做合并（merge）。下面将讨论3种复杂程度不一的数据结构，他们都有效地支持merge操作，使得一次merge操作的运行时间是O(logN)。

六、左式堆

对于合并操作，直观的理解是将一个集合中的数据移到另一个集合中。对于数组，任何一个元素的插入都可能带来N个元素的移动。因此，所有支持有效合并的数据机构都需要使用链式数据结构。
左式堆(leftist heap)像二叉堆一样具有结构性和有序性，它也是二叉树。左式堆与二叉堆的不同之处在于：左式堆不是理想平衡的(perfectly balanced)，而实际上它趋向于非常不平衡。
ps：左式堆与二叉堆不同之一：二叉堆用数组实现，左式堆同二叉树一样，用链表实现。

（一）左式堆的性质

零路径长(null path length)npl：从该节点到一个不具有两个儿子的节点的最短路径的长。具有0个或1个儿子的节点的npl为0，而npl(null)=-1。
左式堆的性质是：对于堆中的每一个节点X，左儿子的npl大于等于右儿子的npl。
这个性质使得左式堆偏重于使树向左增加深度（这也是它名字的由来）。因为左式堆趋向于加深左路径，所有右路径应该短。

定理6.2 在右路径上有r个节点的左式树必然至少有2^r>-1个节点。

从这个定理可以得到，N个节点的左式树有一条右路径最多含有[log(N+1)]_向下取整（就是树的深度）。对左式堆操作的一般思路是将所有的工作放到右路径上进行，它保证树深度最短。需要解决的问题是，insert和merge可能会破坏左式堆性质。

（二）左式堆操作

合并操作

左式堆的基本操作是合并，插入只是合并的特殊情形，可一个把插入看做是单节点堆与一个大的堆的merge。
各个节点，除数据、左引用和右引用所用空间外，每个节点还要有一个只是零路径长的项。
假设有两个堆d1和d2，d1的根值小于d2的跟值，合并的步骤如下：

1. 如果d1和d2中有一个为空，那么直接返回另一个。
2. 首先，我们递归地将具有小的根值的堆(d1)的右子堆合并到大根值堆(d2)的右子堆上。具体合并方法暂不讲解。
3. 接着，我们让这个新的堆成为d1的右儿子。
4. 最后得到的堆满足堆序性，但是在根节点处不满足左式堆的要求，因为此时根的左子树的npl小于右子树的npl。所以，将根的左子堆和右子堆交换并更新零路径长，就完成了merge。

合并两个左式堆的时间界为O(logN)。（why？）
上面步骤2的合并有递归和非递归两种方式，递归方式便于编程而不易理解，非递归方式恰恰相反。（两种方式的描述在书本170~171页）

插入操作

我们可以通过把被插入项看成单节点堆并执行一次merge来完成插入

删除操作

为了执行deleteMin，我们只需去掉根而得到两个堆，然后再将这两个堆合并即可，因此，执行的时间为O(logN)。

七、斜堆(skew heap)

斜堆(Skew Heap)基于左倾堆的概念，也是一个用于快速合并的堆结构，但它可自我调整(self-adjusting)，每一个merge操作的平摊成本仍为O(logN)，其中N为结点数，而且和左倾堆相比，每个结点没有npl属性，从而节省了空间。斜堆并不能保证左倾，但是每一个合并操作（也是采取右路合并）同时需要无条件交换（而左倾堆中只是根据左右子树的npl值不符合要求时才交换）左右子树，让新合并的右子树变成左子树，原来的左子树变成新的右子树（这有点类似于Splay Tree中的做法），从而可以达到平摊意义上的左倾效果。注意：一颗子树r和NULL子树合并时并不需要交换r子树的左右子树。
由于斜堆并不是严格的左倾堆，最坏的情况下右路长度可能为N，因此采用递归调用merge的风险是出现stack overflow。

八、二项队列

左式堆和斜堆在进行合并、插入和deleteMin时均花费O(logN)时间，但还是有改进的余地。
我们知道，二叉堆的插入花费常数平均时间。二项队列支持所有这三种操作，每次操作的最坏情形运行时间为O(logN)，而插入操作平均花费常数时间。

（一）二项队列的结构

参见博客：http://www.cnblogs.com/hapjin/p/5468817.html
二项队列不是一棵树，它是一个森林，由一组堆序的树组成的深林，叫做二项队列。

二项队列有几个性质比较重要：

• 每一颗树都是一个有约束的堆序树，叫做二项树
• 高度为k的第k个二项树Bk由一个根节点和B0, B1, …….B(k-1)构成
• 高度为k的二项树的结点个数为2^k

（二）二项队列的操作

找出最小元

最小元可以通过搜索所有树的树根来找出，由于最多有logN颗不同的树，因此找到最小元的时间可以为O(logN)。如果我们预留一个位置来记录最小元位置，并在其他操作期间更新它，那么可以以O(1)时间执行这个操作。

合并merge

合并操作基本上是通过不断将两个队列中高度相同的二项树合并，直至没有高度相同的二项树为止。
合并两颗二项树的操作花费常数时间，而总共有logN棵二项树，因此合并操作在最坏情形下花费时间O(logN)。

插入

插入实际上是合并的特殊情况，因为我们只要创建一棵单节点树并执行一次合并即可，这种操作的最坏情形运行时间也是O(logN)。平均时间是常数时间。

deleteMin

deleteMin可以通过如下步骤完成：

• 首先找出一棵具有最小根的二项树B_k
• 将该树从原始的森林H中去掉，并形成新的二项树队列H’
• 将B_k的根去掉，得到一些二项树B₀、B₁……B_k-1，它们共同形成优先队列H”
• 合并H’和H”
• 操作结束

找出含有最小值的二项树并创建队列H’和H”花费时间O(logN)。合并这两个队列又花费O(logN)时间，因此，整个deleteMin操作花费O(logN)时间。

（三）二项队列的实现

二项队列是在内在中如何存储的呢？
首先是需要一个一维数组。该数组中的每个元素存储一棵二项树的根结点指针。
除了需要一维数组存储各棵树的根结点外，当然还需要保存各棵二项树了，二项树的采用的是链表表示。
二项树的每一个节点包括数据、左儿子和右兄弟。

九、标准库中的优先队列

在Java1.5之前，Java类库中不存在对优先队列的支持。然而在Java1.5中出现了泛型类PriorityQueue，在该类中insert、findMin和deleteMin通过调用add、element和remove而被表示。

参考博客：http://www.cnblogs.com/hapjin/p/5468817.html
http://blog.csdn.net/changyuanchn/article/details/14648463