堆排序是一種高效的排序算法，它利用了堆（Heap）這種數據結構的特性。堆是一個完全二叉樹，且滿足父節點的值大於等於（最大堆）或小於等於（最小堆）其子節點的值。堆排序通過反覆提取堆頂元素（最大值）並調整堆，最終得到有序數組，時間複雜度穩定爲O(n log n)，適合大規模數據排序。

堆的結構與索引關係¶

堆在數組中可以用完全二叉樹表示，若數組索引從0開始：
- 父節點索引爲i時，左子節點索引爲2i + 1，右子節點索引爲2i + 2；
- 子節點索引爲j時，父節點索引爲(j - 1) // 2。

核心操作1：調整堆（Heapify）¶

調整堆的作用是將以節點i爲根的子樹調整爲最大堆。步驟如下：
1. 初始化當前節點i爲最大值位置；
2. 比較i的左右子節點，找出最大值的子節點索引；
3. 若最大值子節點大於當前節點，交換兩者，並遞歸調整被交換的子節點。

def heapify(arr, n, i):
    largest = i  # 假設當前節點是最大值
    left = 2 * i + 1
    right = 2 * i + 2

    # 若左子節點更大，更新最大值位置
    if left < n and arr[left] > arr[largest]:
        largest = left
    # 若右子節點更大，更新最大值位置
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 若最大值不是當前節點，交換並遞歸調整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

核心操作2：構建最大堆¶

構建最大堆需從最後一個非葉子節點開始，逐步向上調整每個節點，確保整個數組滿足最大堆性質。最後一個非葉子節點的索引爲n // 2 - 1（n爲數組長度）。

def build_max_heap(arr):
    n = len(arr)
    # 從最後一個非葉子節點開始向上調整
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

堆排序主函數¶

堆排序的邏輯是：先構建最大堆，再反覆交換堆頂元素與堆尾元素，同時調整堆以維持最大堆性質，最終得到有序數組。

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)  # 構建最大堆

    # 逐個提取堆頂元素（最大值）並調整堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交換堆頂與當前末尾元素
        heapify(arr, i, 0)  # 調整剩餘元素爲最大堆
    return arr

示例演示¶

以數組[12, 11, 13, 5, 6, 7]爲例：
1. 構建最大堆：
初始數組：[12, 11, 13, 5, 6, 7]
從最後一個非葉子節點（索引2，值13）開始調整，逐步向上處理，最終得到最大堆：[13, 12, 11, 5, 6, 7]。

2. 提取最大值並調整：
   - 交換堆頂（13）與末尾元素（7），數組變爲[7, 12, 11, 5, 6, 13]，調整堆後得到[12, 7, 11, 5, 6, 13]；
   - 重複交換堆頂與末尾元素，最終數組變爲[5, 6, 7, 11, 12, 13]。

總結¶

堆排序通過構建最大堆和調整堆實現高效排序，核心是理解堆的結構和調整邏輯。Python實現中，heapify函數是關鍵，它確保堆的性質，而build_max_heap和heap_sort函數則串聯起整個排序流程。堆排序是原地排序，空間複雜度爲O(1)，時間複雜度爲O(n log n)，適用於大數據量場景。