二叉堆是一種特殊的堆，二叉堆是完全二元樹或者是近似完全二元樹。二叉堆滿足堆特性：父結點的鍵值總是大於或等於任何一個子節點的鍵值。
存儲
二叉堆一般用數組來表示。例如，根節點在數組中的位置是0，第n個位置的子節點分別在2n+1和 2n+2。因此，第0個位置的子節點在2和3，1的子節點在4和5。以此類推。這種存儲方式便於尋找父節點和子節點。
如下圖的兩個堆：
1 11
/ /
2 3 9 10
/ / / /
4 567 5 67 8
/ / / /
89 10 11 12 34
將這兩個堆保存在以1開始的數組中：
位置:123456789 10 11
左圖:123456789 10 11
右圖: 119 1056781234
基本操作
在二叉堆上可以進行插入節點、刪除節點、取出值最小的節點、減小節點的值等基本操作。
如何讓a*尋路更快？元帥三顧茅廬，請來南陽二叉堆先生幫忙優化尋找“開啓士兵名錄”中最低f值的過程，將尋路速度提高了2到3倍，而且越大的地圖效果越明顯。下面隆重介紹二叉堆先生：
下圖是一個二叉堆的例子，形式上看，它從頂點開始，每個節點有兩個子節點，每個子節點又各自有自己的兩個子節點；數值上看，每個節點的兩個子節點都比它大或和它相等。
在二叉堆裏我們要求：
* 最小的元素在頂端
* 每個元素都比它的父節點大，或者和父節點相等。
衹要滿足這兩個條件，其他的元素怎麽排都行。如上面的例子，最小的元素10在最頂端，第二小的元素20在10的下面，但是第三小的元素24在20的下面，也就是第三層，更大的30反而在第二層。
這樣一“堆”東西我們在程序中怎麽用呢？幸運的是，二叉堆可以用一個簡單的一維數組來存儲，如下圖所示。
假設一個元素的位置是n（第一個元素的位置為1，而不是通常數組的第一個索引0），那麽它兩個子節點分別是 n × 2 和 n × 2 + 1 ，父節點是n除以2取整。比如第3個元素（例中是20）的兩個子節點位置是6和11，父節點位置是1。
對於二叉堆我們通常有三種操作：添加、刪除和修改元素：
* 添加元素
首先把要添加的元素加到數組的末尾，然後和它的父節點（位置為當前位置除以2取整，比如第4個元素的父節點位置是2，第7個元素的父節點位置是3）比較，如果新元素比父節點元素小則交換這兩個元素，然後再和新位置的父節點比較，直到它的父節點不再比它大，或者已經到達頂端，及第1的位置。
* 刪除元素
刪除元素的過程類似，衹不過添加元素是“嚮上冒”，而刪除元素是“嚮下沉”：刪除位置1的元素，把最後一個元素移到最前面，然後和它的兩個子節點比較，如果較小的子節點比它小就將它們交換，直到兩個子節點都比它大。
* 修改元素
和添加元素完全一樣的“嚮上冒”過程，衹是要註意被修改的元素在二叉堆中的位置。
可以看出，使用二叉堆衹需很少的幾步就可以完成排序，很大程度上提高了尋路速度。
關於二叉堆先生需要瞭解的就是這麽多了，下面來看看他怎麽幫助元帥工作：
* 每次派出的“預備士兵”都會獲得一個唯一的編號（id），一直到尋路結束，它所有的數據包括位置、f值、g值、“父將”編號都將按這個id存儲。
* 每次有新的“開啓士兵”加入，二叉堆先生將它的編號加入“開啓士兵名錄”並重新排序，使f值最低的id始終排在最前面
* 當有“開啓士兵”晉為“關閉將軍”，刪除“開啓士兵名錄”的第一個元素並重新排序
* 當某個“開啓士兵”的f值被修改，更新其數據並重新排序
註意，“開啓士兵名錄”裏存的衹是人員的編號，數據全都另外存儲。不太明白？沒關係，元帥將在 第三部分 來次真刀實槍的大演兵。 |