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

堆是一棵完全二叉樹

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

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

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

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

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

堆排序

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

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

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

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

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

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

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

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

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

下面給出通過Python中的heapq模塊實(shí)現(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模塊，對(duì)于推排序需要了解堆排序中的建堆過程。

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

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

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

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

def heap_sort(array): 
    n = len(array) 
    # 從尾部開始建堆，這樣保證子節(jié)點(diǎn)有序 
    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：堆元素個(gè)數(shù)，i：堆建頂位置 
def _shift(array, n, i): 
    # 如果沒有子節(jié)點(diǎn)，直接返回 
    if i*2+1 >= n: 
        return 
    # 取最大子節(jié)點(diǎn)位置 
    maxsub = i*2+2 if i*2+2 < n and array[i*2+1] <= array[i*2+2] else i*2+1 
    # 如果節(jié)點(diǎn)小于最大子節(jié)點(diǎn)，交換元素，遞歸以子節(jié)點(diǎn)為堆頂重建 
    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)定的排序算法，因?yàn)樵谂判虻倪^程，存在將堆的最后一個(gè)節(jié)點(diǎn)跟堆頂節(jié)點(diǎn)互換的操作，所以就有可能改變值相同數(shù)據(jù)的原始相對(duì)順序。堆排序整體的時(shí)間復(fù)雜度是O(nlogn)  。

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