一、什麼是堆排序？¶
堆排序是一種利用“堆”這種數據結構進行排序的算法。堆是一種特殊的完全二叉樹，我們可以把它想象成一棵“金字塔”——大頂堆的金字塔尖最大，下面的節點都比它小；小頂堆則相反，尖最小，下面的節點都比它大。堆排序通常使用大頂堆來排序，每次取出堆頂的最大值，逐步完成整個數組的排序。
二、堆的基本概念¶
-
堆的定義：堆是一棵完全二叉樹（每一層都從左到右填滿，最後一層可能不填滿），且滿足以下性質：
- 大頂堆：每個父節點的值都大於或等於子節點的值（根節點是最大值）。
- 小頂堆：每個父節點的值都小於或等於子節點的值（根節點是最小值）。 -
數組表示堆：爲了方便操作，堆通常用數組表示。對於數組中索引爲
i的節點：
- 左子節點索引：2i + 1
- 右子節點索引：2i + 2
- 父節點索引：(i - 1) // 2（整數除法）
三、堆排序的核心思想¶
堆排序的核心是“先建堆，再排序”：
1. 構建堆：將待排序數組轉換爲大頂堆（或小頂堆），此時堆頂元素是數組中的最大值（或最小值）。
2. 取出堆頂並調整：將堆頂元素（最大值）與數組末尾元素交換，此時末尾元素已排好序；然後將剩餘元素重新調整爲堆，重複此過程，直到所有元素排序完成。
四、堆排序的實現步驟¶
以大頂堆爲例，具體步驟如下：
步驟1：構建大頂堆
- 從數組的最後一個非葉子節點開始，向上逐層調整，確保每個節點都滿足“父節點 ≥ 子節點”的大頂堆性質。
- 關鍵操作：堆化（Heapify）。對於一個節點，比較它與左右子節點，將最大值交換到當前節點位置，然後遞歸調整子節點，直到子樹也滿足大頂堆性質。
步驟2：排序過程
- 交換堆頂元素（最大值）與數組末尾未排序元素，此時末尾元素已排好序。
- 堆的大小減1（排除已排序的末尾元素），重新對剩餘元素進行堆化，重複上述交換和堆化，直到堆中只剩一個元素。
五、堆排序的代碼示例（Python）¶
爲了更直觀，用Python實現堆排序的核心邏輯：
def heap_sort(arr):
n = len(arr)
# 步驟1：構建大頂堆（從最後一個非葉子節點開始向上堆化）
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i) # 堆化函數
# 步驟2：排序過程
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 交換堆頂（最大值）與末尾元素
heapify(arr, i, 0) # 調整剩餘元素的堆結構
return arr
def heapify(arr, n, i):
# 堆化函數：以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) # 遞歸調整子樹
六、時間複雜度詳解¶
堆排序的時間複雜度可以從兩個部分分析：
-
構建堆的時間複雜度：
構建堆時，需要從最後一個非葉子節點開始向上堆化，共需n/2次堆化操作。每次堆化的時間複雜度是O(log k)（k爲當前堆的高度），但整體計算下來，構建堆的總時間複雜度是 O(n)（可理解爲所有節點的堆化操作總和接近n）。 -
排序過程的時間複雜度：
排序過程需要執行n-1次堆化（每次取出堆頂後調整剩餘元素），每次堆化的時間複雜度是O(log n)（堆的高度爲log n）。因此，排序過程總時間複雜度爲O(n log n)。
總結：堆排序的總時間複雜度爲 O(n log n)（最好、最壞、平均情況均爲 O(n log n)），空間複雜度爲 O(1)（原地排序，僅需常數額外空間）。
七、堆排序的特點¶
- 穩定性：不穩定（例如數組 [3, 2, 2] 排序後可能變成 [3, 2, 2]，但原數組中兩個2的相對順序可能被改變）。
- 適用場景：適合大規模數據排序，尤其是內存有限時（原地排序）。
八、總結¶
堆排序通過“構建堆→取出堆頂→調整堆”的循環過程，將無序數組轉化爲有序數組。其核心優勢是時間複雜度穩定在 O(n log n)，適合處理大數據量。雖然實現過程稍複雜，但邏輯清晰，是排序算法中的經典選擇。