堆通常是一個可以被看做一棵樹(完全)的數(shù)組對象。且總是滿足以下規(guī)則：

堆是一棵完全二叉樹

節(jié)點總是大于(或小于)它的孩子節(jié)點。

因此，根據(jù)第二個特性，就把二叉堆分為大頂堆(或叫最大堆)，和小頂堆(或叫最小堆)。

在上圖中，1 2 是大頂堆 ，3 4 是小頂堆。判斷是不是堆的條件：「從根結(jié)點到任意結(jié)點路徑上結(jié)點序列的有序性!大頂堆和小頂堆判斷序列是順序還是逆序!」

Python并沒有提供“堆”這種數(shù)據(jù)類型，它是直接把列表當成堆處理的。Python提供的heapq包中有一些函數(shù)，提供執(zhí)行堆操作的工具函數(shù)

>>> import heapq 
>>> heapq.__all__ 
['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop'] 

堆排序

往堆中插入一個元素后，我們就需要進行調(diào)整，讓其重新滿足堆的特性，這個過程叫做堆化(heapify)。

那么堆排序的基本思路是怎么樣的呢?

1. 將待排序序列構(gòu)建成一個堆 H[0……n-1]，根據(jù)(升序降序需求)選擇大頂堆或小頂堆;
2. 把堆首(最大值)和堆尾互換;
3. 順著節(jié)點所在的路徑，向上或者向下，對比，然后交換，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應位置;

下面舉個例子(資源來自王爭算法)，比如在上面的大頂堆中添加數(shù)據(jù)22。

堆化非常簡單，就是順著節(jié)點所在的路徑，向上或者向下，對比，然后交換。

堆排序的刪除操作，這里一般指的是堆頂元素，當我們刪除堆頂元素之后，就需要把第二大的元素放到堆頂，那第二大元素肯定會出現(xiàn)在左右子節(jié)點中。

然后我們再迭代地刪除第二大節(jié)點，以此類推，直到葉子節(jié)點被刪除。但是這樣會產(chǎn)生一個數(shù)組空洞的問題。

因此，這里面又個技巧，就是刪除堆頂元素的時候，不能直接刪除，要用堆頂元素和最后一個元素做交換，然后根據(jù)堆的特點調(diào)整堆，直到滿足條件。

排序的過程就是每次待排序的序列長度減去1再執(zhí)行這兩步。

下面給出通過Python中的heapq模塊實現(xiàn)的堆排序簡單代碼。

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模塊，對于推排序需要了解堆排序中的建堆過程。

將數(shù)組原地建成一個堆。不借助另一個數(shù)組，就在原數(shù)組上操作。建堆的過程，有兩種思路。

第一種建堆思路的處理過程是從前往后處理數(shù)組數(shù)據(jù)，并且每個數(shù)據(jù)插入堆中時，都是從下往上堆化。而第二種實現(xiàn)思路，是從后往前處理數(shù)組，并且每個數(shù)據(jù)都是從上往下堆化。

• 補充：利用層序遍歷(遍歷方式還有前中后)映射到數(shù)組后，假設樹或子樹的根節(jié)點為arr[root],則其對應的子節(jié)點分別為arr[root*2+1],arr[root*2+2]。

也就是如果節(jié)點的下標是 i，那左子節(jié)點的下標就是 2∗i+1，右子節(jié)點的下標就是 2∗i+2，父節(jié)點的下標就是 。

def heap_sort(array): 
    n = len(array) 
    # 從尾部開始建堆，這樣保證子節(jié)點有序 
    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：堆元素個數(shù)，i：堆建頂位置 
def _shift(array, n, i): 
    # 如果沒有子節(jié)點，直接返回 
    if i*2+1 >= n: 
        return 
    # 取最大子節(jié)點位置 
    maxsub = i*2+2 if i*2+2 < n and array[i*2+1] <= array[i*2+2] else i*2+1 
    # 如果節(jié)點小于最大子節(jié)點，交換元素，遞歸以子節(jié)點為堆頂重建 
    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] 

堆排序不是穩(wěn)定的排序算法，因為在排序的過程，存在將堆的最后一個節(jié)點跟堆頂節(jié)點互換的操作，所以就有可能改變值相同數(shù)據(jù)的原始相對順序。堆排序整體的時間復雜度是O(nlogn)  。

參考資料 https://github.com/MaoliRUNsen/runsenlearnpy100