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)。