[Algorithm] 用 Heap 實作 Huffman Code

Heap 的原理

Heap（堆）是一種特殊的資料結構，基於完全二元樹（Complete Binary Tree）的形式。它滿足「堆屬性」（Heap Property），用來高效管理優先權元素，常見於優先權佇列（Priority Queue）的實作中。Heap 分為兩種：

• Min-Heap（最小堆）：每個父節點的值小於或等於其子節點的值。根節點是整個堆的最小元素。
• Max-Heap（最大堆）：每個父節點的值大於或等於其子節點的值。根節點是整個堆的最大元素。

Heap 的原理在於：

• 完全二元樹結構：樹的所有層級（除最後一層外）都完全填滿，最後一層的節點從左到右填充。這使得 Heap 可以用陣列高效表示，而不需要指標。
• 在陣列中，對於索引 i 的節點：
• 左子節點：2i + 1
• 右子節點：2i + 2
• 父節點：(i — 1) // 2

Heap Property 的維護：透過「上浮」（Bubble Up / Swim）和「下沉」（Bubble Down / Sink）操作來維持屬性。

• 上浮：插入新元素後，如果違反屬性，元素向上與父節點交換，直到滿足。
• 下沉：移除根元素後，將最後元素移到根，再向下與較小的子節點交換，直到滿足。

時間複雜度：

• 建堆（Heapify）：O(n)
• 插入（Insert）：O(log n)
• 提取極值（Extract Min/Max）：O(log n)
• 查詢極值（Peek）：O(1)

Heap 的優勢在於高效的極值操作，適合如 Huffman Coding、Dijkstra 演算法、Top-K 問題等應用。

Heap 的實作

pseudo code 如下：

class MinHeap:
    heap = []  # 陣列

    def insert(value):
        heap.append(value)  # 加到最後
        bubble_up(len(heap) - 1)  # 上浮

    def bubble_up(index):
        while index > 0:
            parent = (index - 1) // 2
            if heap[index] < heap[parent]:
                swap(heap[index], heap[parent])
                index = parent
            else:
                break

    def extract_min():
        if len(heap) == 0: return None
        min_val = heap[0]
        heap[0] = heap.pop()  # 最後元素移到根
        bubble_down(0)  # 下沉
        return min_val

    def bubble_down(index):
        size = len(heap)
        while True:
            left = 2 * index + 1
            right = 2 * index + 2
            smallest = index
            if left < size and heap[left] < heap[smallest]:
                smallest = left
            if right < size and heap[right] < heap[smallest]:
                smallest = right
            if smallest != index:
                swap(heap[index], heap[smallest])
                index = smallest
            else:
                break

    def heapify(arr):  # 從陣列建堆
        for i in range(len(arr)//2 - 1, -1, -1):
            bubble_down(i)

• 建堆（Heapify）：從最後一個非葉節點開始，向下沉每個節點。
• 注意：實作中需處理邊界條件，如空堆或單元素。

為什麼霍夫曼編碼會用到 Heap？

霍夫曼編碼的建構過程需要反覆選取頻率最小的兩個節點進行合併，直到只剩一個根節點。這涉及到頻繁的「找出最小值」和「插入新元素」操作。如果使用簡單的陣列或列表，每次找出最小值需要 O(n) 時間（掃描整個列表），對於 n 個符號，總時間複雜度會是 O(n²)，效率低下。

為了優化這一點，我們使用最小堆（Min-Heap）來實現優先權佇列（Priority Queue）。原因如下：

高效選取最小元素：

• Min-Heap 的頂端永遠是堆中最小元素。
• 提取最小元素（extract_min）的時間複雜度是 O(log n)，因為只需調整堆結構。
• 在霍夫曼編碼中，我們需要反覆提取兩個最小頻率節點（extract_min 兩次），合併後插入新節點（insert），每個操作都是 O(log n)。

總時間複雜度優化：

• 初始建堆：O(n)。
• 對於 n 個葉節點，我們進行 n-1 次合併，每次合併涉及 2 次 extract_min 和 1 次 insert，總共約 3(n-1) 次 O(log n) 操作。
• 因此，總時間複雜度為 O(n log n)，遠優於 O(n²)。

實際實作考量：

• Heap 支援動態插入和刪除，適合霍夫曼過程中的節點合併（新內部節點的頻率是兩個子節點的和，需要插入回堆中）。
• 在程式語言如 Python（heapq 模組）或 Java（PriorityQueue）中，這是標準實作方式。
• 如果符號數量很大（如文字壓縮中的大量字元），Heap 的效率優勢更明顯。