數據結構二叉堆能夠很好的實現優先隊列的基本操作。

當一顆二叉樹的每個結點都大於等於它的兩個子結點時，被稱為堆有序。相應地，在堆有序的二叉樹中，每個結點都小於等於它的父節點。從任意結點向下，我們可以得到一列非遞增的元素；從任意結點向上，我們可以得到一列非遞減的元素。

我們可以用長度為N+1的私有數組來表示一個大小為N的堆（我們不會使用pq[0]）。

在堆的有序化時我們會遇到兩種情況。當某個結點的優先順序上升（或是在堆底加入一個新的元素）時，我們需要由下至上恢復堆的順序；當某個結點的優先順序下降（比如將根節點替換為一個較小的元素）時，我們需要由上至下來恢復堆的順序。

• 由下至上的堆有序化 如果堆的有序狀態因為某個結點大於其父節點而被打破，那麼我們就需要通過交換它和它

  的父結點來修復堆。我們可以一遍遍地用同樣的方法來恢復順序，將其不斷向上移動，直

  到遇到一個比它要大的父節點。我們可以利用位置為k的結點其父結點的位置為[k/2]來實 現，演算法如下：

• 由key上至下的堆有序化如果堆的有序狀態被某節點比其子結點更小而打破了，我們可以通過將其和其兩個子節點中較大的者交換來恢復堆。我們同樣要不斷地用相同的方法來恢復順序，直到它的所有子結點都比它更小或到達堆的地步。由位置為k的結點的子結點的位置為2k或2k+1便可以實現。演算法如下：

當我們要向堆中插入元素時，我們將新元素放到數組末尾，然後對其調用swim()方法；當我們要從堆中刪除元素時，我們將數組的最後一個元素放到數組頂端，然後對其調用sink()方法。實現如下：

插入操作和刪除操作的用時和隊列長度成對數關係。

我們將所有元素插入到一個查找最小元素的優先隊列，然後再重複調用刪除最小元素的操作來將它們按照順序刪去。這種基於堆的優先隊列的排序方法便是堆排序。

堆排序可以分為兩個階段。

在堆的構造階段中，我們將原始數組重新組織安排到一個堆中；然後再堆的下沉排序階段，我們從堆中按照遞減順序取出所有元素並得到排序結果。演算法如下：

推薦閱讀：

相關文章