Heap 是一種特別的完全二元樹（Complete Binary Tree），在一顆二元樹中，若除最後一層外的其他層都是充滿節點的，並且最後一層要麼是滿的，要麼在右邊缺少連續若干節點，則此二元樹為完全二元樹。

堆積還可以分成兩種 :

• Max Heap: 父節點的值恆大於等於子節點的值，同層的節點間則不比較，所以和二元搜尋樹的差別就是堆積內的值沒有經過大小排序
• Min Heap: 父節點的值恆小於等於子節點的值

假設二元堆積的值用陣列儲存，i 是母節點 x 的索引，則 :

• 根節點 : i = 0
• 左子節點 : 2 * i + 1
• 右子節點 : 2 * i + 2

範例圖示:

例如節點 19 的索引 1，其左右子節點分別為 3, 4。

Heap 各項資料操作的時間複雜度(Avg Case)

這邊分享一個 Binary Heap 的動畫，從動畫可以更清楚瞭解資料節點是怎麼更新的。

這裡以 Max heap 為例 :

• 從無開始建立堆積: O(n)，實作概念是從上往下、由左至右的順序插入節點，如果插入的值比父節點大，就和父節點交換，反覆直到父層節點一定大於其子節點
• 插入節點: O(log n)，從未完滿的子樹新增節點，如果新結點比父節點大，就和父節點交換，反覆直到父層節點一定大於其子節點
• 更新節點的值: O(log n)，更新指定節點的值後，如果更新的值比父節點大，就和父節點交換，反覆直到父層節點一定大於其子節點
• 移除節點: O(log n)，將要移除的節點值更新成整個 heap 中最大，因此它會不斷的移動到堆積頂部，然後再將它移除，接著的行為就和取得當前堆積頂元素相同
• 取得當前堆積頂元素: O(log n)，將最大的根節點可以直接根據索引值取出，而取出後最下層最右邊的節點去補根節點的位置，若新的根節點比其子節點小，就和子節點交換，反覆直到父層節點一定大於其子節點

上面幾項功能的實作程式碼可以在這個 Github repo javascript-data-structure/Heap 找到!

Heap 的應用

參考 堆積 Wiki

1. Top-k Problems，例如維護一個清單中，根據某些數據排名前幾的資料
2. Dijkstra 演算法
3. 取出許多的值當中，最大 or 最小值也很快速