跳轉到

7.1 二元堆積與heap sort#

概念說明#

二元堆積 是一棵完全二元樹（除最後一層外全滿，最後一層靠左），並滿足堆積性質：最大堆積中每個父節點 ≥ 其子節點；最小堆積則相反。因為形狀完全固定，堆積可以用陣列表示，索引關係（0 起算）：

  • 節點 i 的左小孩：2i + 1，右小孩：2i + 2
  • 節點 i 的父節點：(i - 1) // 2

零指標、連續記憶體、快取友善——堆積是「陣列表示法」的完美範例。Python 的 heapq 模組就是最小堆積的官方實作，操作的是普通 list。

核心操作：上浮與下沉#

  1. 上浮（sift-up / percolate-up）：新元素放在陣列尾端，不斷與父節點比較，若違反堆積性質就交換，直到父節點夠大或抵達頂端。用於插入。
  2. 下沉（sift-down / heapify）：把頂端元素取走後，將尾端元素搬到頂端，不斷與「較大的小孩」交換下沉，直到滿足性質。用於取出最值與建堆。
  3. 建堆（build-heap）：對所有非葉節點（n//2 - 1 到 0）由後往前做下沉。看似 O(n log n)，實際分析總成本是 O(n)——因為絕大多數節點都很淺。

Python 實作#

class MaxHeap:
    def __init__(self):
        self._a = []

    def __len__(self):
        return len(self._a)

    def peek(self):
        return self._a[0]

    def push(self, x):
        a = self._a
        a.append(x)
        i = len(a) - 1
        while i > 0:                      # 上浮
            p = (i - 1) // 2
            if a[p] >= a[i]:
                break
            a[p], a[i] = a[i], a[p]
            i = p

    def pop(self):
        a = self._a
        top, last = a[0], a.pop()         # 尾端元素
        if a:
            a[0] = last
            self._sift_down(0)
        return top

    def _sift_down(self, i):
        a, n = self._a, len(self._a)
        while True:
            l, r, big = 2*i + 1, 2*i + 2, i
            if l < n and a[l] > a[big]:   big = l
            if r < n and a[r] > a[big]:   big = r
            if big == i:
                break
            a[i], a[big] = a[big], a[i]
            i = big

h = MaxHeap()
for x in [4, 1, 7, 3, 9, 2]:
    h.push(x)
print(h.peek())                # 9
print([h.pop() for _ in range(len(h))])   # [9, 7, 4, 3, 2, 1] 由大到小

heap sort#

堆積排序的步驟：

  1. 建最大堆：原地對陣列做 build-heap，O(n)。
  2. 反覆取最值：把堆頂（最大）與堆尾交換，堆大小減一，對新頂做下沉；重複 n−1 次。

每次交換後最大值「沉」到陣列尾端，最終陣列由小到大排序。全程原地進行，空間 O(1)。

def heap_sort(a):
    n = len(a)
    def sift_down(i, size):
        while True:
            l, r, big = 2*i + 1, 2*i + 2, i
            if l < size and a[l] > a[big]:   big = l
            if r < size and a[r] > a[big]:   big = r
            if big == i:
                break
            a[i], a[big] = a[big], a[i]
            i = big
    for i in range(n // 2 - 1, -1, -1):     # 建堆 O(n)
        sift_down(i, n)
    for end in range(n - 1, 0, -1):         # 每次取最大放尾端
        a[0], a[end] = a[end], a[0]
        sift_down(0, end)

data = [5, 3, 8, 1, 9, 2, 7]
heap_sort(data)
print(data)      # [1, 2, 3, 5, 7, 8, 9]

複雜度分析#

操作 時間
push / pop O(log n)
peek O(1)
建堆 O(n)
heap sort O(n log n)，空間 O(1)，不穩定

heap sort 的最壞情況保證 O(n log n)（不像快排有 O(n²) 風險），但快取局部性不如快排，實測通常較慢；它常用於「混合排序」的兜底階段（如 introsort）。

練習#

  1. 把 MaxHeap 改成支援 (priority, item) 元組的最小堆積，並實作「Top-K 大」函式：從 100 萬筆資料中找最大的 10 筆，複雜度應為 O(n log k)。
  2. heap sort 是不穩定的排序（相等元素順序可能改變）。請構造一個具體例子示範，並說明若把 (值, 原索引) 當作鍵即可穩定。
  3. 實作 heapify(list) 的原地版本，並用實驗驗證「建堆是 O(n) 而非 O(n log n)」：n 從 10⁴ 增到 10⁶，比較建堆耗時與 n log n 的成長比例。