什麼是堆？¶
想象你有一堆文件，想優先處理最重要的（比如緊急文件），或者優先處理最不重要的（比如垃圾文件）。這時候，“堆”就像一個特殊的“容器”，能讓你快速拿到最大或最小的那個元素。
堆其實是一種特殊的完全二叉樹，它的核心特點是：每個父節點的值都滿足某種規則（小於或等於/大於或等於子節點）。這種規則讓堆能高效地獲取“最大”或“最小”的元素，就像一個“優先隊列”。
堆的結構基礎：完全二叉樹¶
堆的底層是一棵完全二叉樹。完全二叉樹有什麼特點呢？
- 每一層都填滿了節點，除了最後一層可能不填滿；
- 最後一層的節點從左到右依次排列，沒有“跳過”。
舉個例子：
1
/ \
3 2
/ \ /
6 4 5
這是一個完全二叉樹，每一層都儘量填滿，最後一層（第3層）有3個節點（6、4、5），從左到右排列。
最小堆 vs 最大堆¶
堆有兩種類型，核心區別在於父節點和子節點的大小關係：
最小堆（Min-Heap）¶
- 規則：父節點的值 小於或等於 所有子節點的值。
- 堆頂：最小的元素（根節點）。
例子（數組表示）：
最小堆用數組存儲時，數組的索引對應節點位置，規則是：
- 左子節點索引 = 2×父節點索引 + 1
- 右子節點索引 = 2×父節點索引 + 2
- 父節點索引 = (子節點索引 - 1) // 2
比如數組 [1, 3, 2, 6, 4, 5] 表示的最小堆：
- 堆頂（索引0）是1（最小）；
- 1的左子節點（索引1）是3，右子節點（索引2）是2，滿足 1 ≤ 3 且 1 ≤ 2；
- 3的左子節點（索引3）是6，右子節點（索引4）是4，滿足 3 ≤ 6 且 3 ≤ 4；
- 2的左子節點（索引5）是5，滿足 2 ≤ 5。
最大堆（Max-Heap）¶
- 規則：父節點的值 大於或等於 所有子節點的值。
- 堆頂：最大的元素（根節點）。
例子（數組表示）：
數組 [10, 5, 8, 3, 2, 1] 表示的最大堆：
- 堆頂（索引0）是10（最大）；
- 10的左子節點（索引1）是5，右子節點（索引2）是8，滿足 10 ≥ 5 且 10 ≥ 8；
- 5的左子節點（索引3）是3，右子節點（索引4）是2，滿足 5 ≥ 3 且 5 ≥ 2；
- 8的左子節點（索引5）是1，滿足 8 ≥ 1。
堆的數組表示與索引關係¶
堆最常用數組存儲，因爲完全二叉樹的結構天然適合數組索引。記住這個“父子索引公式”：
- 對於數組中索引爲 i 的節點：
- 左子節點：2*i + 1
- 右子節點：2*i + 2
- 父節點：(i - 1) // 2（整數除法）
比如數組 [1, 3, 2, 6, 4, 5]（最小堆）：
- 節點1（索引0）的子節點是3（索引1）和2（索引2）；
- 節點3（索引1）的子節點是6（索引3）和4（索引4）；
- 節點2（索引2）的子節點是5（索引5）。
堆的基本操作：插入與刪除¶
堆的核心優勢是插入和刪除操作效率極高（時間複雜度 O(log n)），因爲堆的高度是 log n（n 爲元素個數）。
1. 插入操作（以最小堆爲例）¶
步驟：
1. 把新元素放到數組的末尾（即最後一個位置）；
2. 從新元素開始，向上“上浮”（上濾）：比較該元素與父節點的值，如果新元素更小（最小堆），則交換，直到父節點更小或到達堆頂。
例子：
原最小堆數組：[1, 3, 2, 6, 4, 5]（堆頂1）
插入新元素 0：
- 先放到末尾：數組變成 [1, 3, 2, 6, 4, 5, 0]；
- 上浮：0 的父節點是索引3（值6），0 < 6，交換 → [1, 3, 2, 0, 4, 5, 6]；
- 繼續上浮：0 的父節點是索引1（值3），0 < 3，交換 → [1, 0, 2, 3, 4, 5, 6]；
- 繼續上浮：0 的父節點是索引0（值1），0 < 1，交換 → [0, 1, 2, 3, 4, 5, 6]。
現在數組滿足最小堆性質，插入完成。
2. 刪除操作（以最小堆爲例）¶
步驟：
1. 刪除堆頂元素（最小元素）；
2. 把數組最後一個元素放到堆頂；
3. 從堆頂開始，向下“下沉”（下濾）：比較該元素與子節點的值，如果子節點更小（最小堆），則交換，直到子節點更大或到達葉子節點。
例子：
原最小堆數組：[0, 1, 2, 3, 4, 5, 6]（堆頂0）
刪除堆頂元素：
- 先刪除0，數組變成 [1, 2, 3, 4, 5, 6]；
- 把最後一個元素6放到堆頂：數組變成 [6, 2, 3, 4, 5, 6]？不對，原數組長度是7，刪除後長度6，最後一個元素是6（索引5），放到堆頂（索引0）：[6, 2, 3, 4, 5, 6]？
- 下沉：6 的子節點是2（索引1）和3（索引2），最小子節點是2，6 > 2，交換 → [2, 6, 3, 4, 5, 6]；
- 繼續下沉：6 的子節點是4（索引3）和5（索引4），最小子節點是4，6 > 4，交換 → [2, 4, 3, 6, 5, 6]；
- 繼續下沉：6 的子節點是5（索引5），6 > 5，交換 → [2, 4, 3, 5, 6, 6]；
- 此時堆頂2，子節點4（4>2）和3（3>2），滿足最小堆，刪除完成。
堆的應用場景¶
堆最經典的應用是優先隊列，即“每次取出優先級最高（最大/最小）的元素”。以下是常見場景：
1. 優先隊列（任務調度）¶
- 比如服務器處理任務，按優先級（緊急程度）排序，用最大堆每次取最高優先級任務；
- 醫院急診室按病情緊急度排序，用最大堆快速取出最緊急的病人。
2. 找第k大的數¶
- 用最小堆維護前k大的數，堆頂就是第k大的數。例如找第3大的數：
- 遍歷數組，保持堆大小爲3，新元素比堆頂大則替換並調整堆，最後堆頂就是第3大的數。
3. 哈夫曼編碼（壓縮算法）¶
- 用最小堆合併頻率最低的兩個節點，構建哈夫曼樹，用於數據壓縮。
總結¶
堆是一種基於完全二叉樹的特殊結構，核心是“父節點與子節點的大小關係”。最小堆和最大堆分別用於快速獲取最小或最大元素，通過插入（上浮）和刪除（下沉）操作維護堆的性質。堆的 O(log n) 操作效率使其成爲優先隊列、第k大元素等問題的首選數據結構。
對於初學者，建議從數組表示和插入/刪除步驟入手，通過具體例子（如上文的插入刪除過程）理解堆的邏輯，再逐步應用到實際問題中。堆的應用廣泛且實用，掌握它能極大提升算法效率哦！