Heap

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

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

注意

Heap 不是二元搜尋樹（BST）！
Heap 不保證左子節點和右子節點誰大誰小，它只管 「父節點與子節點」 的上下關係。

實作

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

因為 Heap 是一棵完全二元樹，節點由上到下、由左到右非常緊密，所以不需要像一般的樹結構一樣用複雜的 pointer 連來連去。我們可以直接用一個 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 {
  constructor() {
    this.values = [];
  }

  /*
    新增元素：O(log N)

    在尾端加入 Node，新加入的值會和 parent 的值比較
    如果大於 parent 則交換位置（稱為 Bubble Up）
    直到整個 Heap 的狀態符合 parent 大於 children 的情況。
   */
  insert(val) {
    if (val === undefined) return this.values;
    this.values.push(val);
    if (this.values.length > 1) {
      this.bubbleUp();
    }
    return this.values;
  }

  bubbleUp() {
    let idx = this.values.length - 1;
    
    // 當前 Node 還不是 Root 時，持續檢查
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      
      // 如果當前 Node value 大於 parent，則進行交換
      if (this.values[idx] > this.values[parentIdx]) {
        [this.values[idx], this.values[parentIdx]] = [this.values[parentIdx], this.values[idx]];
        idx = parentIdx; // 繼續往上追蹤
      } else {
        break; // 符合最大堆積特性，提早結束
      }
    }
  }

  /**
   取出最大值：O(log N)

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

    const max = this.values[0];
    // 用最後一個元素覆蓋根節點，並移出末端元素
    this.values[0] = this.values.pop();
    
    // 如果移除後還有剩餘元素，執行向下調整
    if (this.values.length > 0) {
      this.sinkDown();
    }
    return max;
  }

  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];

    while (true) {
      let leftIdx = 2 * idx + 1;
      let rightIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swapIdx = null; // 用來記錄這輪應該跟誰交換（左、右或都不換）

      // 1. 安全檢查：確認左子節點是否存在
      if (leftIdx < length) {
        leftChild = this.values[leftIdx];
        // 如果左子節點比目前節點大，暫定與左子節點交換
        if (leftChild > element) {
          swapIdx = leftIdx;
        }
      }

      // 2. 安全檢查：確認右子節點是否存在
      if (rightIdx < length) {
        rightChild = this.values[rightIdx];
        // 右子節點要勝出的條件：
        // 情況 A：目前節點比右子節點小（swapIdx 仍是 null），且右子節點存在。
        // 情況 B：左右子節點都比目前節點大（swapIdx 已是 leftIdx），但右子節點比左子節點更大。
        if (
          (swapIdx === null && rightChild > element) || 
          (swapIdx !== null && rightChild > leftChild)
        ) {
          swapIdx = rightIdx;
        }
      }

      // 3. 檢查終止條件：如果 swapIdx 依然是 null，代表目前節點已經比左右子節點都大，不需要再換了
      if (swapIdx === null) break;

      // 4. 執行交換，並更新索引繼續下一輪
      [this.values[idx], this.values[swapIdx]] = [this.values[swapIdx], this.values[idx]];
      idx = swapIdx;
    }
  }
}

複雜度

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 來動態挑選下一個距離最近的節點。