堆排序以及最大優先隊列

來自：聰聰的個人網站

作者：lufficc

鏈接：https://lufficc.com/blog/heap-sort-and-max-priority-queue

堆排序（heapsort）是一種比較快速的排序方式，它的時間複雜度為O(nlgn)，而且堆排序具有空間原址性：即任何時候只需要有限（常數個）的空間來存儲臨時數據。而且堆排序還被應用在構造優先順序隊列中，本文將會用Java實現一個最大堆，並利用最大堆實現優先順序隊列。

最大堆的性質

1、是一棵近似的完全二叉樹，除了最底層，其它是全滿，且從左向右填充。

2、樹的每個節點對應數組一個元素，根節點對應數組下標0元素。

3、對於下標i，它的父節點下標為(i + 1) / 2 - 1，左孩子節點下標為i * 2 + 1，右孩子節點下標為i * 2 + 2。

4、最大堆中，每個結點都必須大於等於左右孩子節點。

堆排序

1、維護最大堆

為了建立一個最大堆，我們需要設計一個演算法來維護最大堆的性質。對於節點i，我們假設它們的左右子樹都是最大堆，而節點i因為小於左右孩子而違背了最大堆的性質，因此我們需要對節點i進行逐級下降，從而使得以節點i為根結點的子樹滿足最大堆的性質。

上述代碼的解釋是：

對於節點i（即數組下標i）,首先獲取它的左右子孩子下標，分別存儲到l，r變數中，其中left和right函數可以根據最大堆的性質得到，如下：

變數length是要維護的數組的長度，它的值

交換之後，節點max的值變成了較小的原來節點i的值，因此，以節點max為根節點的子樹可能違背最大堆的性質。注意到此時問題和一開始一模一樣，只是節點i變成了節點max，因此遞歸調用maxHeapify(a, max, length)即可。

如果把第一張圖的節點1的值改為1，這時從節點1開始調用maxHeapify(a, 1, a.length，整個流程如下：

可以看到，在經歷兩次遞歸調用，逐級下沉，原來因為1節點變小，而被打破的最大堆，又重新維護完成。

2、建立最大堆

我們採用自底向上的方法來建立一個最大堆。通過觀察發現，下標為a.length / 2 到a.length - 1的節點均為葉子節點，沒有子孩子。這意味著，它們已經是一個最大堆，只是僅有一個元素。因此，我們只需要自底向上，對其他節點調用maxHeapify來維護最大堆即可：

注意，循環變數從a.length / 2 + 1開始，因為a.length / 2 到a.length - 1的節點滿足最大堆，即a.length / 2 + 1的左右子孩子（如果有的話）是最大堆，符合使用maxHeapify調用條件。如果我們對數組[10, 8, 11, 8, 14, 9, 4, 1, 17]進行建立最大堆，那麼輸出數組為[17, 14, 11, 8, 10, 9, 4, 1, 8]:

點擊播放 GIF/91K

3、堆排序

在第二步建立完成最大堆之後，注意到整個數組的 最大元素 總是在最大堆的第一個，即a[0]。這時，如果我們拿走第一個元素，放到數組的最後一個位置，然後對第一個元素進行維護最大堆maxHeapify，如此循環進行，便可完成整個數組的排序。

這樣我們就完成了對數組的從小到大排序。

最大優先隊列

堆排序是一個優秀的演算法，在操作系統中可以利用最大堆實現最大優先隊列來實現共享計算機系統的作業調度。最大優先隊列記錄各個作業之間的相對優先順序，當某個作業中斷後選出具有最高優先順序的隊列來執行。最大優先順序隊列應該支持如下操作：

1、maximum()：返回堆的最大值。

2、extractMax()：返回堆的最大值並從堆中刪除。

3、heapIncreaseKey(i, key)：將下標為i的元素增大為key。

4、maxHeapInsert(key)：將元素key插入到堆中。

maximum()最簡單，直接返回第一個元素：

extractMax也很簡單，取出第一個後，只需把最後一個元素放到第一個，然後對第一個元素進行維護最大堆即可：

點擊播放 GIF/29K

heapIncreaseKey(i, key)會增大下標為i的元素為key。首先將a[i]的值更新為key，因為增大的a[i]關鍵字可能會違背最大堆的性質，因此我們需要對a[i]進行逐級上升。即將當前元素逐級與父節點比較，如果大於父節點，則與父節點進行交換，一直到當前元素小於父節點為止：

maxHeapInsert(key)十分簡單，因為它等價於數組長度增加一，然後最後一個元素設置為－∞，然後把它增大為key的操作：

點擊播放 GIF/28K

在一個包含n個元素的堆中，所有優先順序隊列的操作都可以在O(lgn)的時間內完成。

源代碼可以在這裡找到：lufficc/Algorithmhttps://github.com/lufficc/Algorithm/tree/master/src/com/lufficc/algorithm/Sort/HeapSort

文章來自自己的理解以及演算法導論。

-- END

最近熱文：

1、邀你參加11期 程序員專場相親活動

2、PHP高工/架構師，18-50K，深圳南山

3、JAVA/Web前端，深圳前海，15-30K

4、如何判斷是否到了該辭職的時候？

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！