二叉堆
二叉堆
二叉堆是一種特殊的堆，二叉堆是完全二元樹或者是近似完全二元樹。二叉堆滿足堆特性：父結點的鍵值總是大於或等於任何一個子節點的鍵值。
二叉堆一般用數組來表示。例如，
點在數組中的位置是0，第n個位置的子節點分別在2n+1和 2n+2。因此，第0個位置的子節點在2和3，1的子節點在4和5。以此類推。這種存儲方式便於尋找父節點和子節點。
如下圖的兩個堆：
1 11
/ \ / \
2 3 9 10
/ \ / \ / \ / \
4 5 6 7 5 6 7 8
/ \ / \ / \ / \
8 9 10 11 1 2 3 4
將這兩個堆保存在以1開始的數組中：
位置: 1 2 3 4 5 6 7 8 9 10 11
左圖: 1 2 3 4 5 6 7 8 9 10 11
右圖: 11 9 10 5 6 7 8 1 2 3 4
在二叉堆上可以進行插入節點、刪除節點、取出值最小的節點、減小節點的值等基本操作。