淺析經典排序算法之堆排序
堆通常是一個可以被看做一棵樹(完全)的數組對象。且總是滿足以下規則：
堆是一棵完全二叉樹
節點總是大于(或小于)它的孩子節點。
因此，根據第二個特性，就把二叉堆分為大頂堆(或叫最大堆)，和小頂堆(或叫最小堆)。
在上圖中，1 2 是大頂堆 ，3 4 是小頂堆。判斷是不是堆的條件：「從根結點到任意結點路徑上結點序列的有序性!大頂堆和小頂堆判斷序列是順序還是逆序!」
Python并沒有提供“堆”這種數據類型，它是直接把列表當成堆處理的。Python提供的heapq包中有一些函數，提供執行堆操作的工具函數
- >>> import heapq
- >>> heapq.__all__
- ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']
堆排序
往堆中插入一個元素后，我們就需要進行調整，讓其重新滿足堆的特性，這個過程叫做堆化(heapify)。
那么堆排序的基本思路是怎么樣的呢?
- 將待排序序列構建成一個堆 H[0……n-1]，根據(升序降序需求)選擇大頂堆或小頂堆;
- 把堆首(最大值)和堆尾互換;
- 順著節點所在的路徑，向上或者向下，對比，然后交換，目的是把新的數組頂端數據調整到相應位置;
下面舉個例子(資源來自王爭算法)，比如在上面的大頂堆中添加數據22。
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然后交換。
堆排序的刪除操作，這里一般指的是堆頂元素，當我們刪除堆頂元素之后，就需要把第二大的元素放到堆頂，那第二大元素肯定會出現在左右子節點中。
然后我們再迭代地刪除第二大節點，以此類推，直到葉子節點被刪除。但是這樣會產生一個數組空洞的問題。
因此，這里面又個技巧，就是刪除堆頂元素的時候，不能直接刪除，要用堆頂元素和最后一個元素做交換，然后根據堆的特點調整堆，直到滿足條件。
排序的過程就是每次待排序的序列長度減去1再執行這兩步。
下面給出通過Python中的heapq模塊實現的堆排序簡單代碼。
- from heapq import heappop, heappush
- def heap_sort(array):
- heap = []
- for element in array:
- heappush(heap, element)
- ordered = []
- while heap:
- ordered.append(heappop(heap))
- return ordered
- array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
- print(heap_sort(array))
- # [2, 4, 5, 13, 15, 17, 18, 21, 24, 26]
如果不使用heapq模塊，對于推排序需要了解堆排序中的建堆過程。
將數組原地建成一個堆。不借助另一個數組，就在原數組上操作。建堆的過程，有兩種思路。
第一種建堆思路的處理過程是從前往后處理數組數據，并且每個數據插入堆中時，都是從下往上堆化。而第二種實現思路，是從后往前處理數組，并且每個數據都是從上往下堆化。
- 補充：利用層序遍歷(遍歷方式還有前中后)映射到數組后，假設樹或子樹的根節點為arr[root],則其對應的子節點分別為arr[root*2+1],arr[root*2+2]。
也就是如果節點的下標是 i，那左子節點的下標就是 2∗i+1，右子節點的下標就是 2∗i+2，父節點的下標就是 。
- def heap_sort(array):
- n = len(array)
- # 從尾部開始建堆，這樣保證子節點有序
- for i in range((n-1)//2, -1, -1):
- _shift(array, n, i)
- # 依次把堆頂元素交換到最后，重建堆頂（堆不包含剛交換的最大元素）
- for i in range(n-1, 0, -1):
- array[0], array[i] = array[i], array[0]
- _shift(array, i, 0)
- return array
- # 重建堆頂元素 n：堆元素個數，i：堆建頂位置
- def _shift(array, n, i):
- # 如果沒有子節點，直接返回
- if i*2+1 >= n:
- return
- # 取最大子節點位置
- maxsub = i*2+2 if i*2+2 < n and array[i*2+1] <= array[i*2+2] else i*2+1
- # 如果節點小于最大子節點，交換元素，遞歸以子節點為堆頂重建
- if array[i] < array[maxsub]:
- array[i], array[maxsub] = array[maxsub], array[i]
- _shift(array, n, maxsub)
- if __name__ == '__main__':
- array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
- print(heap_sort(array))
- # [2, 4, 5, 13, 15, 17, 18, 21, 24, 26]
堆排序不是穩定的排序算法，因為在排序的過程，存在將堆的最后一個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。堆排序整體的時間復雜度是O(nlogn) 。
參考資料 https://github.com/MaoliRUNsen/runsenlearnpy100
