[Data Structure] 堆積

堆積 (Heap) 是一種以完全二元樹 (Complete Binary Tree) 為形狀約束、並滿足堆積性質 (Heap Property) 的資料結構。堆積讓「取出最大值（或最小值）」的操作穩定為 $O(\log n)$，是優先佇列 (Priority Queue) 的標準實作。

完全二元樹

• 除了最後一層，其餘每層都要填滿
• 最後一層的節點全部靠左排列

這個形狀限制是為了讓整棵樹可以用一個連續陣列表達，不需要節點物件 + 指標。

Max-heap 與 Min-heap

兩種堆積的差別只在「誰在上面」：

陣列表示法

把完全二元樹「層序」攤平到陣列。以 1-indexed 為例（實作較直觀）：

• 節點 $i$ 的父節點：$\lfloor i / 2 \rfloor$
• 節點 $i$ 的左子：$2i$
• 節點 $i$ 的右子：$2i + 1$

若用 0-indexed：

• 父節點：$\lfloor (i - 1) / 2 \rfloor$
• 左子：$2i + 1$
• 右子：$2i + 2$

以 max-heap [_, 6, 5, 4, 1, 2, 3]（1-indexed，_ 代表 index 0 保留不用，讓 $i \cdot 2$、$i \cdot 2 + 1$ 的公式直接對上位置）為例：

         6  (index 1)
        / \
       5   4
      /|   |
     1 2   3

以下互動圖解把這棵樹與陣列並排呈現，點任一節點就能即時看到它的 index 與 parent / left / right 公式的計算結果：

核心操作

以下所有操作都用 1-indexed 表示法。隨時記得：index $i$ 的父 = $\lfloor i / 2 \rfloor$、左子 = $2i$、右子 = $2i + 1$。「葉節點」定義為 index 落在 $\lfloor n/2 \rfloor + 1 \sim n$ 範圍的節點（下方沒有子）。

Insert — 向上浮 (Sift Up)

步驟：

1. 把新元素放在陣列尾端（index = 當前 size + 1，維持完全二元樹形狀）
2. 令 $i$ = 新元素目前的 index；比較 $\text{arr}[i]$ 與父 $\text{arr}[\lfloor i/2 \rfloor]$
3. 若違反堆積性質（max-heap 中子 > 父）就 swap，然後 $i \leftarrow \lfloor i/2 \rfloor$（往上爬一層）
4. 重複步驟 2–3，直到符合性質或 $i = 1$（已到根）

從空的 max-heap 依序 insert [3, 1, 6, 5, 2, 4]（1-indexed）：

最終 max-heap：

         6
        / \
       5   4
      /|   |
     1 2   3

以下動畫逐步重現上面六次 insert 的 sift-up 過程——新插入的節點會先落在陣列尾端，再往上和父節點比較：

• 時間複雜度：$O(\log n)$（最多爬樹高那麼多層）

Extract Max — 向下沉 (Sift Down)

取出根（最大值）的步驟：

1. 記錄 $\text{arr}[1]$ 當作回傳結果
2. 把最後一個元素（$\text{arr}[n]$）搬到 index 1，刪除尾端（維持完全二元樹形狀）
3. 令 $i = 1$；讀左子 $\text{arr}[2i]$ 與右子 $\text{arr}[2i+1]$（若存在），挑兩者中較大者的 index 為 $c$
4. 若 $\text{arr}[i] <$ $\text{arr}[c]$ 則 swap，接著 $i \leftarrow c$（下沉到較大的子節點）
5. 重複步驟 3–4，直到符合性質或 $i$ 沒有子節點（即 $2i > n$，$i$ 已是葉）

承上例 [_, 6, 5, 4, 1, 2, 3]，連續執行兩次 extract max：

第一次 extract：

回傳 6，剩下 [_, 5, 3, 4, 1, 2]。

第二次 extract：

回傳 5。

以下動畫從 [_, 6, 5, 4, 1, 2, 3] 開始連續執行 extract max，觀察取出順序與每次 sift-down 的過程——你會發現取出順序恰好是遞減，這就是 Heap Sort 的核心：

• 時間複雜度：$O(\log n)$

Build Heap — 一次蓋好整個堆積

把無序陣列轉成堆積的兩種做法：

1. 連續 insert：空堆積起，對每個元素呼叫 insert。總成本 $O(n \log n)$
2. Floyd’s Heapify：從最後一個非葉節點（index $\lfloor n / 2 \rfloor$）開始，逐一向下 sift down。總成本 $O(n)$

Floyd’s 版本較快的直覺：越接近葉子節點越多、但下沉高度越小；越接近根節點下沉高度越大、但數量越少。整體可證明為 $O(n)$。

以 [3, 1, 6, 5, 2, 4]（$n = 6$）做 Floyd’s heapify，1-indexed 為 [_, 3, 1, 6, 5, 2, 4]，從 index $\lfloor 6/2 \rfloor = 3$ 開始往 1 做 sift down：

最終與 insert 版結果相同：[_, 6, 5, 4, 1, 2, 3]。

複雜度總覽

• 查詢 $O(n)$ 是因為堆積只保證父子關係、沒有排序結構，只能線性掃描

Heap Sort（堆積排序）

把堆積拿來排序的自然應用，原地排序、$O(n \log n)$、不穩定：

1. 對陣列做 Build Heap（max-heap）→ $O(n)$
2. 反覆：把根（最大值）與當前堆積尾端交換，堆積大小減 1，對新根做 sift down → 共 $n - 1$ 次、每次 $O(\log n)$

以 [3, 1, 6, 5, 2, 4] 為例（1-indexed，排序區以粗體標記在陣列尾端）：

| 步驟 | 動作 | 陣列狀態（排序區用 | 分隔）| | :---: | :--- | :--- | | 1 | Build max-heap | [, 6, 5, 4, 1, 2, 3] | | 2 | swap idx 1 與 6（堆積大小 6 → 5），sift down 3 | [, 5, 3, 4, 1, 2 | 6] | | 3 | swap idx 1 與 5（5 → 4），sift down 2 | [, 4, 3, 2, 1 | 5, 6] | | 4 | swap idx 1 與 4（4 → 3），sift down 1 | [, 3, 1, 2 | 4, 5, 6] | | 5 | swap idx 1 與 3（3 → 2），sift down 2 | [, 2, 1 | 3, 4, 5, 6] | | 6 | swap idx 1 與 2（2 → 1），sift down 1 | [, 1 | 2, 3, 4, 5, 6] | | 7 | 堆積只剩 1 個元素，結束 | [1, 2, 3, 4, 5, 6] |

結果為遞增陣列。若想遞減排序則改用 min-heap。

優先佇列 (Priority Queue)

優先佇列 抽象資料型別：每個元素帶有「優先級 (priority)」，每次取出的都是當前優先級最高（或最低）者。

Java 的 PriorityQueue、Python 的 heapq、C++ STL 的 priority_queue 底層皆為堆積。

import java.util.PriorityQueue;

public class PQExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();  // 預設 min-heap
        pq.offer(3); pq.offer(1); pq.offer(6); pq.offer(5); pq.offer(2); pq.offer(4);

        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");  // 1 2 3 4 5 6
        }
    }
}

Heap 的實作

以 1-indexed max-heap 為例。

import java.util.ArrayList;

public class MaxHeap {
    private ArrayList<Integer> heap = new ArrayList<>();

    public MaxHeap() {
        heap.add(0);  // index 0 當作保留
    }

    public int size() { return heap.size() - 1; }
    public boolean isEmpty() { return size() == 0; }
    public int peek() { return heap.get(1); }

    public void insert(int value) {
        heap.add(value);
        siftUp(heap.size() - 1);
    }

    public int extractMax() {
        int max = heap.get(1);
        int last = heap.remove(heap.size() - 1);
        if (!isEmpty()) {
            heap.set(1, last);
            siftDown(1);
        }
        return max;
    }

    private void siftUp(int i) {
        while (i > 1) {
            int parent = i / 2;
            if (heap.get(i) > heap.get(parent)) {
                swap(i, parent);
                i = parent;
            } else break;
        }
    }

    private void siftDown(int i) {
        int n = heap.size() - 1;
        while (2 * i <= n) {
            int left = 2 * i;
            int right = 2 * i + 1;
            int largest = (right <= n && heap.get(right) > heap.get(left)) ? right : left;
            if (heap.get(largest) > heap.get(i)) {
                swap(i, largest);
                i = largest;
            } else break;
        }
    }

    private void swap(int a, int b) {
        int tmp = heap.get(a);
        heap.set(a, heap.get(b));
        heap.set(b, tmp);
    }
}

常見考法

複雜度推導

Insert / Extract $O(\log n)$：

Floyd’s Build Heap $O(n)$：高度為 $h$ 的節點數 $\le \lceil n / 2^{h+1} \rceil$，每個節點下沉最多 $h$ 層：

（$\sum h / 2^{h+1} = 1$ 是常見等比加權和。）

Heap Sort $O(n \log n)$：Build $O(n)$ + $n-1$ 次 extract × $O(\log n)$ = $O(n \log n)$

堆積在經典演算法中的角色

許多圖論與貪婪演算法的效能關鍵就在於優先佇列——而優先佇列的主流實作就是堆積。