1.2　优先队列

原理1　优先队列的实现原理

在算法设计中经常需要从序列中查找最值（最小值或最大值），例如最短路径、哈夫曼编码等都需要查找最小值。若顺序查找最值需要O(n)时间，而使用优先队列（priority queue）查找最值只需O(1)时间，则入队和出队需要O(logn)时间。

在树形结构中有两种比较特殊的二叉树：满二叉树和完全二叉树。

满二叉树：指一棵深度为k且有2k-1个节点的二叉树。满二叉树的每一层都“充满”节点，达到最大节点数。

完全二叉树：除了最后一层，每一层都是满的（达到最大节点数），最后一层节点是从左向右出现的。深度为k的完全二叉树，其每个节点都与深度为k的满二叉树中的节点一一对应。完全二叉树和上图中的满二叉树节点一一对应。完全二叉树除了最后一层，前面每一层都是满的，最后一层必须从左向右排列。也就是说，若2没有左子节点，则2不可以有右子节点，若2没有右子节点，则3不可以有左子节点。

性质：若对完全二叉树从上至下、从左至右编号，则编号为i的节点其左子节点编号必为2i，其右子节点编号必为2i+1；其双亲编号必为i/2。

例如，有一棵完全二叉树，2号节点的双亲节点为1，左子节点为4，右子节点为5；3号节点的双亲节点为1，左子节点为6，右子节点为7。

若每一个节点的值都大于或等于左右子节点的值，则称之为最大堆（大顶堆或大根堆）；若每一个节点的值都小于或等于左右子节点的值，则称其为最小堆（小顶堆或小根堆）。可以将堆看作一棵完全二叉树的顺序存储结构，一个数据元素序列及其对应的完全二叉树如下图所示，该完全二叉树满足最大堆的定义。

普通队列是先进先出的，优先队列与普通队列不同，每次出队时都按照优先级顺序出队。优先队列是通过堆实现的，优先队列中的元素存储满足堆的定义。上图中每一个节点的值都大于或等于左右子节点的值，满足最大堆的定义，是最大值优先的最大堆。

优先队列有出队和入队两种基本操作。

1. 出队

出队时，堆顶（队头）出队，最后一个元素代替堆顶的位置，重新调整为堆。

完美图解：

一个最大堆如下图所示。出队时，堆顶30出队，最后一个元素12代替堆顶。

出队后，除了堆顶，其他节点都满足最大堆的定义，只需堆顶执行下沉操作，即可调整为堆。下沉指堆顶与左右子节点比较，若比子节点大，则已调整为堆；若比子节点小，则与较大的子节点交换，交换到新的位置后继续向下比较，从根节点一直比较到叶子。

堆顶下沉的过程如下。

（1）堆顶12和两个子节点28、20比较，比子节点小，与较大的子节点28交换。

（2）12再和两个子节点16、18比较，比子节点小，与较大的子节点18交换。

（3）比较到叶子时停止，已调整为堆。

调整堆的过程就是堆顶从根下沉到叶子的过程。

算法代码：

2. 入队

入队时，将新元素放入最后一个元素之后，重新调整为堆。

完美图解：

例如29入队，首先将29放入最后一个元素12的后面。

入队后除了新入队的元素，其他节点都满足最大堆的定义，只需新元素执行上浮操作，即可调整为堆。上浮指新元素与其父节点比较，若小于或等于父节点，则已调整为堆；若比父节点大，则与父节点交换，交换到新的位置后，继续向上比较，从叶子一直比较到根。

新元素上浮的过程如下。

（1）新元素29和其父节点18比较，比父节点大，与父节点交换。

（2）29再和其父节点28比较，比父节点大，与父节点交换。

（3）29再和其父节点30比较，比父节点小，已调整为堆。

算法代码：

3. 算法分析

优先队列是利用堆实现的一种特殊队列，堆是按照完全二叉树顺序存储的，有n个节点的完全二叉树的高度为+1。出队时，堆顶元素出队，最后一个元素代替堆顶，新的堆顶从根下沉到叶子，最多达到树的高度，时间复杂度为O(logn)；入队时，新元素从叶子上浮到根，最多达到树的高度，时间复杂度也为O(logn)。