优先队列（堆）

优先队列（堆）

1.优先队列模型：
优先队列是允许下列两种操作的数据结构：insert（插入）以及deleteMin（删除最小者）。insert操作等价于入队，而deleteMin操作则等价于出队，它的工作是找到，返回并删除优先队列中的最小元素。

2.二叉堆：
结构性质：
堆是一棵完全二叉树---深度为h的二叉树，其他各层的节点数都达到了最大，h层的节点也是从左向右填入的。由于完全二叉树很有规律，所以可以用数组来存储完全二叉树中的节点。该数组0位置空出，从下表为1的位置开始填充。以广度遍历存储。

堆序性质：
父母节点的关键字不大于孩子节点的关键字（除根节点，因为根节点没有父母节点）。这样我们就能很快的找到优先队列中的最小元素。

基本的堆操作：
insert（插入）：
首先我们在堆中下一个位置创建一个空穴。如果待插入元素X放在空穴中不违反堆序性质，那插入完成。否则，我们把空穴的父节点移到空穴中，这样空穴就朝着根的方向上冒一步。继续该过程直到X能被放到空穴中为止。这种策略叫做“上滤”。

deleteMin（删除最小元）：
我们直到堆中最小元为根节点所代表的元素，那么删除最小元就是将根节点删除，然后再根节点处建立一个空穴。由于堆中少了一个元素，因此，堆中最后一个元素X必须移到某个位置。然后我们将空穴的两个儿子中较小的一个放在根节点处，这样就把空穴向下推了一层。重复该步骤直到X可以被放入空穴中。这种策略叫做“下滤”。

其他堆操作：
1.decreaseKey(降低关键字的值)：decreaseKey（p,x）操作降低在位置p处的值，降低幅度为正的量x。由于可能破坏堆序性质，因此必须通过上滤进行调整。该操作可以使程序优先执行。

2.increaseKey（增加关键字的值）：increaseKey（p，x）操作增加在位置p处的值，增加幅度为正的量x。可以用下滤来完成。许多调度程序自动的降低正在过多消耗CPU时间的进程的优先级。

3.delete（删除）：delete（p）操作删除堆中位置p上的节点。该操作优先通过decreaseKey（p，∞）然后在进行deleteMin操作，当一个进程被用户终止时，必须从优先队列中除去。

4.buildHeap(构建堆)：二叉堆是由一些项的初始结合构造而得。可以使用N个相继的insert操作来完成。注意，这个算法中每个insert将花费O（1）平均时间以及O（NlogN）的最坏时间，所以该算法的总运行时间是O（N)而不是O（NlogN）的最坏时间。

3.d-堆
d-堆是二叉堆的推广，它就像二叉堆，只不过所有的节点都有d个儿子（因此二叉堆也可叫做2-堆）。