堆積排序法教學：原理、程式碼與時間複雜度

用白話說明原理

堆積排序就是用更快的方法找最大值的選擇排序。選擇排序每次都掃描整個未排序的部分，成本是 O(n)。堆積排序把未排序的部分維持成堆積，所以最大值永遠在索引 0，移除它之後恢復順序只需 O(log n)。

二元堆積可以不用指標，直接存放在普通陣列中。對索引 i 的元素：

• 左子節點在 2*i + 1，右子節點在 2*i + 2；
• 父節點在 (i - 1) // 2；
• 在最大堆積中，每個父節點都大於或等於它的子節點，所以最大的元素在索引 0。

1. 從陣列建立最大堆積：由最後一個非葉節點開始，讓每個非葉節點下沉，一路處理到索引 0。
2. 把根節點（最大值）與堆積的最後一個元素交換。這個元素現在已在最終位置。
3. 將堆積縮小一格，並讓新的根節點下沉，直到堆積性質再度成立。
4. 重複步驟 2 和 3，直到堆積只剩一個元素。

逐步範例

將 [4, 10, 3, 5, 1] 排序。直線之後的元素已排序並為最終位置。

Python 實作

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

Python 的 heapq 模組在普通串列上提供最小堆積。把每個元素依序彈出，就得到已排序的串列，這是一個簡短（但非原地）的堆積排序：

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

時間與空間複雜度

由下而上建堆是 O(n)，不是 O(n log n)，因為完全二元樹中所有節點高度的總和是 O(n)。整體時間由取出階段主導。

堆積排序與其他排序法的比較

堆積排序不是穩定的：把根節點交換到尾端，可能讓元素越過其他鍵值相同的元素。它的主要優點，是同時擁有保證的 O(n log n) 最差情況與 O(1) 額外空間，這是快速排序和合併排序都做不到的組合。它的弱點在記憶體存取：在索引 i 與 2*i + 1 之間跳來跳去，對 CPU 快取很不友善，所以通常比實作良好的快速排序慢。內省排序（introsort）在快速排序遞迴太深時，就以堆積排序作為後備。

變體與常見錯誤

• 部分排序：若只要最大的 k 個元素，建立堆積後取出 k 次，成本為 O(n + k log n)。Python 的 heapq.nlargest 與 heapq.nsmallest 就是這樣做的。
• 從資料串流取前 k 名：維持一個大小為 k 的最小堆積，對每個新元素做推入或取代，時間 O(n log k)、記憶體 O(k)。
• 由下而上的堆積排序先把空位一路下沉到葉節點，再往上調整，可以省下比較次數。
• 平滑排序（smoothsort）是 Dijkstra 提出的堆積變體，對已排序的輸入可達 O(n)，但因為很複雜，很少使用。

何時使用堆積排序

需要保證 O(n log n) 的最差情況且不能使用額外記憶體時，例如嵌入式或即時系統，或作為其他排序法內部的安全後備，就適合使用堆積排序。在日常的 Python 程式碼中，請使用 sorted()，它是穩定的，而且在典型資料上更快。堆積這個資料結構本身比排序更有用：優先佇列、Dijkstra 最短路徑、排程器、合併 k 個已排序串列（heapq.merge）以及找出最大的 k 個值，全都建立在它之上。面試常問堆積的索引公式、為何建堆是 O(n)，以及前 k 名問題。