Heap (堆積)¶

基本概念¶

定義¶

Complete Binary Tree
Max-Heap: 父節點 ≥ 子節點
Min-Heap: 父節點 ≤ 子節點

Array 表示法¶

Parent(i) = (i-1) / 2
Left(i)   = 2i + 1
Right(i)  = 2i + 2

基本操作¶

Insert (上浮 / Bubble Up)¶

def insert(heap, key):
    heap.append(key)
    i = len(heap) - 1
    # Bubble up
    while i > 0 and heap[parent(i)] < heap[i]:
        swap(heap, i, parent(i))
        i = parent(i)

時間複雜度: \(O(\log n)\)

Extract-Max/Min (下沉 / Heapify Down)¶

def extract_max(heap):
    max_val = heap[0]
    heap[0] = heap.pop()
    heapify_down(heap, 0)
    return max_val

def heapify_down(heap, i):
    largest = i
    l, r = left(i), right(i)
    if l < len(heap) and heap[l] > heap[largest]:
        largest = l
    if r < len(heap) and heap[r] > heap[largest]:
        largest = r
    if largest != i:
        swap(heap, i, largest)
        heapify_down(heap, largest)

時間複雜度: \(O(\log n)\)

Build Heap¶

def build_heap(arr):
    n = len(arr)
    # 從最後一個非葉節點開始
    for i in range(n//2 - 1, -1, -1):
        heapify_down(arr, i)

時間複雜度: \(O(n)\) (不是 O(n log n)!)

複雜度總結¶

操作	時間複雜度
Insert	\(O(\log n)\)
Extract-Max/Min	\(O(\log n)\)
Get-Max/Min	\(O(1)\)
Build Heap	\(O(n)\)
Increase/Decrease Key	\(O(\log n)\)

Heap Sort¶

def heap_sort(arr):
    build_heap(arr)  # O(n)
    for i in range(len(arr)-1, 0, -1):
        swap(arr, 0, i)
        heapify_down(arr, 0, size=i)  # O(log n)

時間: \(O(n \log n)\)
空間: \(O(1)\) (in-place)
不穩定 (not stable)

Priority Queue¶

介面¶

insert(key, priority)
extract_max() / extract_min()
peek()
increase_key() / decrease_key()

實作比較¶

實作方式	Insert	Extract	Peek
Unsorted Array	\(O(1)\)	\(O(n)\)	\(O(n)\)
Sorted Array	\(O(n)\)	\(O(1)\)	\(O(1)\)
Heap	\(O(\log n)\)	\(O(\log n)\)	\(O(1)\)

應用¶

Heap Sort
Priority Queue
Dijkstra's Algorithm - 使用 min-heap
Prim's Algorithm - 使用 min-heap
Huffman Encoding - 使用 min-heap
Top-K 問題 - 維護 size K 的 heap
Median Maintenance - 使用兩個 heap

Huffman Encoding (霍夫曼編碼)¶

目的: 無損資料壓縮，產生最優前綴碼 (Prefix-free code)

演算法 (Greedy + Min-Heap):

1. 為每個字元建立葉節點，頻率為 priority
2. 將所有節點放入 min-heap
3. 重複直到 heap 只剩一個節點:
   a. 取出兩個最小頻率的節點
   b. 建立新的內部節點，頻率 = 兩子節點頻率之和
   c. 將新節點放回 heap
4. 最後剩下的節點即為 Huffman Tree 根

範例: 字元頻率 A:5, B:9, C:12, D:13, E:16, F:45

建樹過程:
1. 取 A(5), B(9) → 新節點 14
2. 取 C(12), D(13) → 新節點 25
3. 取 14, E(16) → 新節點 30
4. 取 25, 30 → 新節點 55
5. 取 F(45), 55 → 根節點 100

        100
       /   \
     F(45)  55
           /  \
         25    30
        / \   /  \
      C  D  14   E
           / \
          A   B

編碼: F=0, C=100, D=101, A=1100, B=1101, E=111

特性: - 頻率高 → 編碼短 - 時間複雜度: \(O(n \log n)\) - 產生最優前綴碼 (任一編碼不是其他編碼的前綴)

Top-K 問題¶

找前 K 大的元素: - 維護 size K 的 min-heap - 遍歷時，若元素 > heap top，替換之 - 時間: \(O(n \log k)\)

Median Maintenance¶

Max-heap 存較小的一半
Min-heap 存較大的一半
保持兩 heap 大小差 ≤ 1
Median 在某個 heap 的 top

進階: Fibonacci Heap¶

操作	Binary Heap	Fibonacci Heap
Insert	\(O(\log n)\)	\(O(1)\)
Extract-Min	\(O(\log n)\)	\(O(\log n)\)
Decrease-Key	\(O(\log n)\)	\(O(1)\) amortized
Merge	\(O(n)\)	\(O(1)\)

Dijkstra with Fibonacci Heap: \(O(E + V \log V)\)