在【資料結構Python描述】二叉堆（heap）簡介和Python手工實作及使用二叉堆實作優先級佇列中，我們學習了什么是二叉堆，以及具體什么是最小堆和最大堆，

通過【資料結構Python描述】自底向上構建二叉堆實作及其 O ( n ) O(n) O(n)時間復雜度分析，我們又學習了如何在給定一個序列（如：串列）的情況下，高效地將其轉換為一個二叉堆，

本文將基于上述兩篇文章的內容，來介紹如何通過最大堆來進行排序，即堆排序，

一、堆排序簡介

1. 理論

如果給定輸入串列A[1..n]，其中n=len(A)，則堆排序演算法需要先構建一個最大堆，即最大元素總是位于根節點處，且所有子節點不大于其父節點，由于最大元素位于根節點A[1]處，因此我們可以通過如下步驟對A進行排序：

• 首先，將根節點和A[n]進行交換，則最大值的位置確定；
• 其次，由于新的根節點可能使得當前完全二叉樹違背堆序性質，因此可以采用元素交換的方式使其重新滿足堆序性質，需要注意的是，此時元素交換時無需再考慮元素A[n]；
• 然后，將新的根節點和A[n-1]進行交換，則次大值的位置確定；
• 再次，由于新的根節點可能使得當前完全二叉樹違背堆序性質，再次采用元素交換的方式使其重新滿足堆序性質，需要注意的是，此時元素交換時無需再考慮元素A[n]和A[n-1]；
• 最后，重復上述程序，直到A[1..n]按照非遞減順序排列，

2. 圖解

2.1 建最大堆

實際上，給定一個串列，建一個最大堆的流程和建一個最小堆的流程基本一致，具體地，針對給定的10個元素串列，建堆步驟如下：

• 首先，同建最小堆一樣，如圖 ( a ) (a) (a)所示，自底向上，先確保以位置5為根節點的完全二叉樹是一個二叉堆，此時滿足最大堆的堆序性質，不涉及元素交換；
• 其次，確保以位置4為根節點的完全二叉樹是一個二叉堆，此時違背了最大堆的堆序性質，需對位置4和位置8的元素進行交換，如結果如圖 ( c ) (c) (c)所示；
• 緊接著，依次確保以位置3，2，1處為根節點的完全二叉樹是一個二叉堆，最終建堆結果如圖 ( f ) (f) (f)所示，

2.2 用最大堆排序

下面是利用上述創建的最大堆進行排序的程序，具體地：

• 首先，將根節點元素16和最底層最右側元素1交換，然后通過元素交換使得不包括16在內的其他節點均滿足堆序性質，結果如圖 ( b ) (b) (b)所示；
• 然后，將根節點元素14和最底層最右側元素1交換，然后通過元素交換使得不包括16和14在內的其他節點均滿足堆序性質，結果如圖 ( c ) (c) (c)所示；
• 重復上述程序，直到所有元素排好序，如圖 ( j ) (j) (j)所示，

二、堆排序實作

由于堆一定是一個二叉樹，而二叉樹的實作可以是基于鏈式結構，也可以基于陣列結構，為降低實作難度，且避免使用鏈式結構導致額外的記憶體開銷（如一個節點保存其父、子節點參考所需的變數），這里使用基于陣列結構來描述二叉樹，

def __down_heap(arr, num, j):
    """
    通過元素交換，確保串列arr[0:num]中，元素arr[j]及其子孫節點滿足堆序性質
    :param arr: 串列形式給出的待排序列
    :param num: 串列索引上限
    :param j: 串列元素的索引
    :return: None
    """
    left = 2 * j + 1  # 元素arr[j]左子節點的索引
    right = 2 * j + 2  # 元素arr[j]右子節點的索引
    if left < num:  # 判斷arr[j]是否有左子節點
        large_child = left
        if right < num:  # 判斷arr[j]是否有右子節點
            if arr[right] > arr[left]:
                large_child = right
        if arr[large_child] > arr[j]:  # 確保最終建成最大堆
            arr[large_child], arr[j] = arr[j], arr[large_child]  # 交換兩個節點處的值使滿足堆序性質
            __down_heap(arr, num, large_child)


def heapify(arr):
    """將串列形式給出的元素視為完全二叉樹，對其進行建堆"""
    for j in range((len(arr) - 1) // 2, -1, -1):  # 建堆
        __down_heap(arr, len(arr), j)


def heap_sort(arr):
    """堆排序"""
    heapify(arr)  # 構建最大堆
    # 依次將最大值，次大值...最小值從右往左排好
    for i in range(len(arr) - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 每一次迭代，將當前堆中最大元素排好序
        __down_heap(arr, i, 0)  # 每迭代一次后元素arr[i]已排好序，僅需確保前i個元素滿足堆序性質


if __name__ == '__main__':
    arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
    heap_sort(arr)
    print(arr)

三、堆排序復雜度

1. 時間復雜度

堆排序的時間復雜度分為兩個部分：

• 一部分是呼叫heapify函式的建最大堆所需的時間開銷，由之前的理論分析可知為 O ( n ) O(n) O(n)；
• 另一部分是回圈呼叫__down_heap方法確保未排序的完全二叉樹為最大堆的時間開銷，可按照如下計算：

l o g ( n ? 1 ) + l o g ( n ? 2 ) + ? ? ? + l o g ( 1 ) = l o g ( ( n ? 1 ) ! ) log(n-1)+log(n-2)+\cdot\cdot\cdot+log(1)=log((n-1)!) log(n?1)+log(n?2)+???+log(1)=log((n?1)!)

而：

l o g ( ( n ? 1 ) ! ) < l o g ( n ! ) < n l o g ( n ) log((n-1)!)<log(n!)<nlog(n) log((n?1)!)<log(n!)<nlog(n)

最后忽略低階項 O ( n ) O(n) O(n)，故最壞時間復雜度為 n l o g ( n ) nlog(n) nlog(n)，

2. 空間復雜度

由上述堆排序的實作代碼可以看出，在堆排序程序中，除了輸入的待排序列和排序程序中使用的輔助變數外，沒有額外的記憶體開銷，因此這是典型的原地排序，故其最壞空間復雜度為 Θ ( n ) \Theta{(n)} Θ(n)，