堆是一種特殊的樹結構，它通常基於完全二叉樹實現，並且滿足大頂堆或小頂堆的性質。簡單來說，堆是一個“特殊的完全二叉樹”，其中每個父節點的值要麼都大於等於子節點（大頂堆），要麼都小於等於子節點（小頂堆）。這種結構讓堆能夠高效地獲取最大值或最小值，因此在算法中應用廣泛。
堆的存儲方式¶
堆通常用數組來存儲，因爲完全二叉樹的結構可以通過數組索引直接映射父子關係。假設數組的索引爲 i（從0開始），那麼：
- 左子節點的索引是 2*i + 1
- 右子節點的索引是 2*i + 2
- 父節點的索引是 (i - 1) // 2（向下取整）
例如，數組中索引爲0的元素是根節點，它的左子節點是索引1，右子節點是索引2；索引1的父節點是索引0，左子節點是索引3，右子節點是索引4，以此類推。
大頂堆 vs 小頂堆¶
- 大頂堆：父節點的值 大於等於 所有子節點的值（根節點是最大值）。
- 小頂堆：父節點的值 小於等於 所有子節點的值（根節點是最小值）。
舉個例子：
- 大頂堆數組：[9, 5, 7, 3, 6, 2, 4]（根節點9最大）
- 小頂堆數組：[3, 6, 5, 9, 7, 2, 4]（根節點3最小）
堆的基本操作¶
堆的核心操作包括 插入、刪除、構建堆、獲取堆頂，這些操作都依賴於堆的調整機制（上浮或下沉）。
1. 插入操作（上浮調整）¶
目的：向堆中添加一個元素，並保持堆的性質。
步驟：
1. 將新元素放在數組末尾（完全二叉樹的最後一個空位）。
2. 從新元素的位置開始，與父節點比較：
- 如果是大頂堆且新元素 大於 父節點，交換兩者位置；
- 如果是小頂堆且新元素 小於 父節點，交換兩者位置。
3. 重複步驟2，直到父節點的性質滿足或到達根節點。
示例（大頂堆插入元素10）：
原大頂堆數組：[9, 5, 7, 3, 6, 2, 4]（長度7）
- 插入10到末尾：[9, 5, 7, 3, 6, 2, 4, 10]
- 新元素在索引7，父節點是 (7-1)//2 = 3（值3），10 > 3，交換 → [9, 5, 7, 10, 6, 2, 4, 3]
- 新元素在索引3，父節點是 (3-1)//2 = 1（值5），10 > 5，交換 → [9, 10, 7, 5, 6, 2, 4, 3]
- 新元素在索引1，父節點是 (1-1)//2 = 0（值9），10 > 9，交換 → [10, 9, 7, 5, 6, 2, 4, 3]
- 到達根節點，插入完成，最終堆數組：[10, 9, 7, 5, 6, 2, 4, 3]
2. 刪除操作（下沉調整）¶
目的：刪除堆頂元素（大頂堆的最大值/小頂堆的最小值），並保持堆的性質。
步驟：
1. 將堆頂元素（數組索引0）與最後一個元素交換，然後刪除最後一個元素。
2. 從新堆頂（原最後一個元素）的位置開始，與子節點比較：
- 如果是大頂堆，比較左右子節點，取 最大值，若堆頂元素 小於 最大值，交換位置；
- 如果是小頂堆，比較左右子節點，取 最小值，若堆頂元素 大於 最小值，交換位置。
3. 重複步驟2，直到堆頂元素的性質滿足或到達葉子節點。
示例（大頂堆刪除堆頂元素10）：
原大頂堆數組：[10, 9, 7, 5, 6, 2, 4]（長度7）
- 堆頂（10）與最後一個元素（4）交換：[4, 9, 7, 5, 6, 2, 10]，刪除最後一個元素，數組變爲 [4, 9, 7, 5, 6, 2]
- 新堆頂在索引0（值4），左右子節點：索引1（9）和索引2（7），取最大值9，4 < 9，交換 → [9, 4, 7, 5, 6, 2]
- 新堆頂在索引1（值4），左右子節點：索引3（5）和索引4（6），取最大值6，4 < 6，交換 → [9, 6, 7, 5, 4, 2]
- 新堆頂在索引4（值4），無有效子節點（超出數組長度），刪除完成，最終堆數組：[9, 6, 7, 5, 4, 2]
3. 構建堆¶
目的：將一個無序數組轉化爲堆。
步驟：
1. 找到最後一個非葉子節點（索引 n//2 - 1，n 爲數組長度）。
2. 從該節點開始，依次向上（即索引遞減）對每個節點執行 下沉調整，直到根節點。
示例（將數組 [3, 1, 2, 6, 4, 5] 構建爲大頂堆）：
- 數組長度 n=6，最後一個非葉子節點索引 6//2 - 1 = 2（值2）
- 處理索引2（值2）：左右子節點索引3（6）和4（4），最大值6，2 < 6，交換 → [3, 1, 6, 2, 4, 5]
- 處理索引1（值1）：左右子節點索引3（2）和4（4），最大值4，1 < 4，交換 → [3, 4, 6, 2, 1, 5]
- 處理索引0（值3）：左右子節點索引1（4）和2（6），最大值6，3 < 6，交換 → [6, 4, 3, 2, 1, 5]
- 調整完成，最終大頂堆數組：[6, 4, 3, 2, 1, 5]
4. 獲取堆頂元素¶
直接返回數組索引0的元素（根節點），即大頂堆的最大值或小頂堆的最小值。
堆的應用¶
堆的高效性使其廣泛用於：
- 優先隊列：如任務調度（按優先級執行任務）、高頻元素統計等。
- 堆排序：時間複雜度 O(n log n)，比冒泡排序、插入排序更高效。
- Top K問題：快速找到數組中前K大/小的元素。
總結¶
堆是一種基於完全二叉樹的特殊結構，通過數組存儲和上浮/下沉調整操作，能高效實現插入、刪除、獲取極值等功能。掌握堆的核心思想，對理解算法（如排序、優先隊列）至關重要。初學者可以從簡單的例子（如用數組模擬堆）入手，逐步熟悉插入和刪除的調整過程。