跳至主要内容

Heap

Binary Heap

Heap（堆積） 是一種非常特殊的 Binary Tree 資料結構，它必須滿足以下兩個嚴格的條件：

  1. 結構特性（完全二元樹 Complete Binary Tree）：
    • 除了最後一層外，其餘各層的節點必須全部填滿
    • 而且最後一層的節點必須由左至右依序填入，不能留空
  2. 堆積特性（Heap Property）：父節點與子節點之間存在固定的順序關係。根據這個關係，Heap 分為兩大類：
    • Max Heap
      • 任何一個父節點的值，都大於或等於它的子節點。因此，Root 一定是整棵樹的最大值。
    • Min Heap
      • 任何一個父節點的值，都小於或等於它的子節點。因此，Root 一定是整棵樹的最小值。
白話理解

想像軍中的排隊場合，長官每次都挑最高的人走，不在乎隊伍長怎樣只在乎「目前這群人裡面誰最高」，並不要求所有人乖乖排成一直線。只要長官隨時能一眼確認最高的人在哪，一旦這個人被請走，剩下的人重新比一下誰最高就好，不需要花時間把所有人重新排序。

Heap 就是這種「只保證極值隨時找得到，其他順序不管」的結構。

Heap 不是二元搜尋樹（BST）

Heap 不保證左子節點和右子節點誰大誰小，它只管 「父節點與子節點」 的上下關係。

實作​

由於 JavaScript 內建沒有提供 Heap 這個資料結構（不像 Python 有 heapq，C++ 有 priority_queue），因此 JavaScript 通常需要自己動手寫一個 Heap。

因為 Heap 是一棵完全二元樹，節點由上到下、由左到右非常緊密，所以不需要像一般的樹結構一樣用複雜的 pointer 連來連去。我們可以直接用一個 Array 來實作：

Storing a binary heap in a list/array

以 Max Heap 為例，任意 Node 的 index 是 i，則

  • Left child 的 index 是 2*i + 1
  • Right child 的 index 是 2*i + 2
  • Parent 的 index 是 (i-1)/2 (小數無條件捨去)
      10 (i=0)
     /   \
    8     7
  (i=1)  (i=2)
   / \
  4   2
(i=3)(i=4)
class MaxBinaryHeap:
    def __init__(self):
        self.values = []

    def insert(self, val):
        """
        新增元素：O(log N)

        在尾端加入 Node，新加入的值會和 parent 的值比較
        如果大於 parent 則交換位置（稱為 Bubble Up）
        直到整個 Heap 的狀態符合 parent 大於 children 的情況。
        """
        if val is None:
            return self.values
        self.values.append(val)
        if len(self.values) > 1:
            self._bubble_up()
        return self.values

    def _bubble_up(self):
        idx = len(self.values) - 1

        # 當前 Node 還不是 Root 時，持續檢查
        while idx > 0:
            parent_idx = (idx - 1) // 2

            # 如果當前 Node value 大於 parent，則進行交換
            if self.values[idx] > self.values[parent_idx]:
                self.values[idx], self.values[parent_idx] = self.values[parent_idx], self.values[idx]
                idx = parent_idx  # 繼續往上追蹤
            else:
                break  # 符合最大堆積特性，提早結束

    def extract_max(self):
        """
        取出最大值：O(log N)

        取出 Root 的值並將最後的 Node 移到 Root 的位置
        接著讓這個值和 children 比較大小
        如果小於 children 則交換位置（這個動作稱為 Sink Down）
        直到整個 Heap 的狀態符合 parent 大於 children 的情況
        """
        if len(self.values) == 0:
            return None
        if len(self.values) == 1:
            return self.values.pop()

        max_val = self.values[0]
        # 用最後一個元素覆蓋根節點，並移出末端元素
        self.values[0] = self.values.pop()

        # 如果移除後還有剩餘元素，執行向下調整
        if len(self.values) > 0:
            self._sink_down()
        return max_val

    def _sink_down(self):
        idx = 0
        length = len(self.values)
        element = self.values[0]

        while True:
            left_idx = 2 * idx + 1
            right_idx = 2 * idx + 2
            left_child = right_child = None
            swap_idx = None  # 用來記錄這輪應該跟誰交換（左、右或都不換）

            # 1. 安全檢查：確認左子節點是否存在
            if left_idx < length:
                left_child = self.values[left_idx]
                # 如果左子節點比目前節點大，暫定與左子節點交換
                if left_child > element:
                    swap_idx = left_idx

            # 2. 安全檢查：確認右子節點是否存在
            if right_idx < length:
                right_child = self.values[right_idx]
                # 右子節點要勝出的條件：
                # 情況 A：目前節點比右子節點小（swap_idx 仍是 None），且右子節點存在。
                # 情況 B：左右子節點都比目前節點大（swap_idx 已是 left_idx），但右子節點比左子節點更大。
                if (swap_idx is None and right_child > element) or (
                    swap_idx is not None and right_child > left_child
                ):
                    swap_idx = right_idx

            # 3. 檢查終止條件：如果 swap_idx 依然是 None，代表目前節點已經比左右子節點都大，不需要再換了
            if swap_idx is None:
                break

            # 4. 執行交換，並更新索引繼續下一輪
            self.values[idx], self.values[swap_idx] = self.values[swap_idx], self.values[idx]
            idx = swap_idx

上面這份手刻的 MaxBinaryHeap 只處理了 Max Heap。如果想要 Min Heap，最直覺的做法是複製一份幾乎一模一樣的程式碼，把 bubbleUp、sinkDown 裡所有的比較方向反過來（> 全部換成 <），但這樣一來，兩份程式碼幾乎相同，只差在比較方向，維護起來很容易顧此失彼。下面分別介紹 Python 內建的解法，以及一份程式碼就能同時支援兩種 Heap 的寫法。

Python 內建的 heapq：預設就是 Min Heap​

Python 標準函式庫的 heapq 模組，直接提供現成的 Heap 操作，不需要自己刻 bubbleUp / sinkDown。要注意的是，heapq 預設實作的是 Min Heap，也就是 heap[0] 永遠是最小值：

import heapq

nums = [5, 3, 8, 1, 9, 2]
heapq.heapify(nums)   # 原地把 list 轉成合法的 min heap 結構：O(n)

heapq.heappush(nums, 4)  # 新增元素：O(log n)
print(nums[0])           # 直接看 index 0，就是目前最小值：O(1) → 1

smallest = heapq.heappop(nums)  # 取出並移除最小值：O(log n)
print(smallest)  # 1

如果需要 Max Heap，heapq 並沒有直接提供，最常見的技巧是把存進去的數字都先取負號，取出時再取一次負號還原：

import heapq

nums = [5, 3, 8, 1, 9, 2]
max_heap = [-n for n in nums]
heapq.heapify(max_heap)   # 對「取負號後的數字」做 heapify，最小的負數 = 原本最大的正數

heapq.heappush(max_heap, -4)  # 新增元素時記得先取負號
print(-max_heap[0])           # 取出時再取一次負號，還原成正確的最大值 → 9

largest = -heapq.heappop(max_heap)  # 取出並移除最大值
print(largest)  # 9
負號技巧的限制

取負號這招只適用於「純數字」的情境。如果 Heap 裡放的是字串、物件，或需要依照多個欄位排序的 tuple，直接取負號就不管用了，這時候通常需要自訂排序邏輯（例如放進 tuple 讓 Python 依序比較），或是改用下面介紹的 Bridge Pattern 寫法。

用 Bridge Pattern 讓一份程式碼同時支援 Min Heap 與 Max Heap​

不管是 Max Heap 還是 Min Heap，bubbleUp 和 sinkDown 的陣列索引運算完全一樣（一樣是 2*i+1、2*i+2、(i-1)/2），唯一的差別只在於「兩個值比較時，誰應該被換到上面」這個判斷方向。

Bridge Pattern 的做法，就是把「Heap 結構本身怎麼運作」和「比較大小的規則」拆成兩塊：Heap 類別只負責處理陣列索引的搬移邏輯，實際的比較規則則透過建構子傳入一個 cmp 函式決定。這樣一來，Min Heap 和 Max Heap 就能共用同一份程式碼，不需要複製貼上再手動反轉每一個比較符號：

def default_cmp(x, y):
    return x > y  # 預設是 maxHeap


class Heap:
    def __init__(self, compare_func=default_cmp):
        self.values = []
        self.cmp = compare_func

    def insert(self, val):
        values, cmp = self.values, self.cmp
        values.append(val)
        index = len(values) - 1
        while index > 0:
            parent_idx = (index - 1) // 2
            if not cmp(values[index], values[parent_idx]):
                return
            values[index], values[parent_idx] = values[parent_idx], values[index]
            index = parent_idx

    def extract(self):
        values, cmp = self.values, self.cmp
        if not values:
            return None

        values[0], values[-1] = values[-1], values[0]
        res = values.pop()
        length = len(values)
        index = 0
        exchange = 2 * index + 1

        while exchange < length:
            right = 2 * index + 2
            if right < length and cmp(values[right], values[exchange]):
                # 如果右子節點存在，且
                # 在 maxHeap 中：右子節點的值 > 左子節點的值
                # 在 minHeap 中：右子節點的值 < 左子節點的值
                exchange = right
            if not cmp(values[exchange], values[index]):
                break
            values[index], values[exchange] = values[exchange], values[index]
            index = exchange
            exchange = 2 * index + 1

        return res

    def peek(self):
        if self.values:
            return self.values[0]
        return None

要切換 Min Heap 或 Max Heap，只需要在建立實例時傳入不同的比較函式：

max_heap = Heap()  # 不傳 compare_func，使用預設的 default_cmp -> Max Heap
for n in [5, 3, 8, 1]:
    max_heap.insert(n)
print(max_heap.peek())    # 8（目前最大值）
print(max_heap.extract()) # 8
print(max_heap.extract()) # 5

min_heap = Heap(lambda x, y: x < y)  # 把比較方向反過來 -> Min Heap
for n in [5, 3, 8, 1]:
    min_heap.insert(n)
print(min_heap.peek())    # 1（目前最小值）
print(min_heap.extract()) # 1
print(min_heap.extract()) # 3

defaultCmp 的意思是「x 應該排在 y 上面嗎？」。

insert 在往上比對時，只要 cmp(child, parent) 成立就往上交換；extract 在往下比對時，只要 cmp(child, current) 成立就往下交換。傳入 (x, y) => x > y，交換條件就變成「子節點比較大就往上換」，結果自然是 Max Heap；傳入 (x, y) => x < y，交換條件反過來，結果就是 Min Heap。

Heap 結構本身的陣列索引運算完全沒有改變，改變的只有「決定誰該在上面」的規則，這正是 Bridge Pattern「把不變的結構，和可以自由抽換的規則拆開」的精神。

複雜度​

Heap 最大的優勢在於動態維護極值。

當我們新增或刪除資料時，它會透過「Heapify」的調整過程，在極短的時間內恢復 Heap 的特性。

操作說明時間複雜度
Get Min/Max直接看陣列第一個元素（Root），取得極值。O(1)
Insert把新元素加到 array 最後面，然後「由下往上」與 parent 比較並交換，直到符合規則。O(log N)
Delete Min/Max移走 Root。將 array 最後一個元素放到 Root，然後「由上往下」與較大/較小的子節點比較並交換。O(log N)

適用情況​

提示

只要遇到 「要動態、即時取得極值」 的情境，Heap 絕對是首選！

  • 優先佇列（Priority Queue）
    • 普通的 Queue 是先進先出，但 Priority Queue 會讓「優先權最高（最大或最小）」的元素先出列。
    • Heap 就是實作 Priority Queue 最完美的底層結構。
  • 尋找第 K 個極值：例如「在 100 萬筆資料中，動態找出前 10 大的數字」（Top K Elements），用 Max Heap 處理效能極高。
  • Heap Sort：利用 Heap 每次拔出 Root（最大或最小值）的特性來排序，時間複雜度是穩定的 O(N logN)，而且不需要額外的記憶體空間。
  • 圖形演算法的優化
    • 例如 Dijkstra's Algorithm（找最短路徑）和 Prim's Algorithm（找最小生成樹），都會用 Min-Heap 來動態挑選下一個距離最近的節點。

常見誤區​

  • 誤以為 Heap 內部是「完全排序好」的：Heap 只保證 Root 一定是最大（或最小）值，除了這個規則之外，其他節點之間並沒有嚴格的大小順序，千萬不要以為把 Heap 的 array 直接印出來就是排序好的結果。
  • 和 Binary Search Tree 搞混：如同文中提醒的，Heap 不保證左右子節點誰大誰小，也不支援像 BST 那樣快速搜尋「任意值」，Heap 只擅長快速取得極值。
  • 忘記處理陣列邊界：實作 bubbleUp 或 sinkDown 時，如果沒有先確認 left/right child 的 index 是否超出陣列長度，很容易讀到 undefined，導致比較結果出錯。
  • 誤以為 Python 的 heapq 預設是 Max Heap：heapq 只提供 Min Heap，heap[0] 永遠是最小值，需要 Max Heap 時要自己用負號技巧，或改用 Bridge Pattern 的寫法。
  • 自訂 cmp 函式時，把交換方向想反：cmp(a, b) 回傳 true 代表「a 應該被換到 b 上面」，如果把回傳值的意義搞反，寫出來的 Heap 順序會整個顛倒（Max Heap 變成 Min Heap，反之亦然），建議寫完後用幾筆資料實際跑一次驗證方向是否正確。
最後於 更新