先說(shuō)思路，后上完整代碼。

新手一定要先學(xué)完全二叉樹，再學(xué)二叉堆,有些人喜歡叫大頂堆小頂堆，也可以叫最小堆最大堆，一個(gè)意思。學(xué)會(huì)最小堆自然明白最大堆，我這里以最小堆為例。

最小堆：所有節(jié)點(diǎn)的值都<=子節(jié)點(diǎn)值。

最大堆：所有節(jié)點(diǎn)的值都>=子節(jié)點(diǎn)值。

首先要記住3個(gè)公式。

完全二叉樹采用數(shù)組存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)更好，因?yàn)殒準(zhǔn)酱鎯?chǔ)需要額外空間存儲(chǔ)左右子節(jié)點(diǎn)。這也是為什么完全二叉樹需要最后一層葉子節(jié)點(diǎn)靠左排列。

每次從末尾插入節(jié)點(diǎn)的時(shí)候，需要和父節(jié)點(diǎn)比較，滿足條件就交換位置，重復(fù)這個(gè)過程直到新插入的節(jié)點(diǎn)<=父節(jié)點(diǎn)或者再無(wú)父節(jié)點(diǎn)，也就是到達(dá)頂部。

看著上圖想象一下這個(gè)過程，假如在末尾新加入節(jié)點(diǎn)0，需要和5交換，再和3交換，最后和1交換，最后達(dá)到一個(gè)從小到大的排列。

移除頭節(jié)點(diǎn)該怎么操作呢？新手朋友可能會(huì)想，從頭結(jié)點(diǎn)開始往下交換不就行了嗎？會(huì)遇到空洞問題，如圖所示。

正確做法如下：

1.直接用頭節(jié)點(diǎn)和末尾節(jié)點(diǎn)進(jìn)行交換

2.移除尾節(jié)點(diǎn).

3.從頭結(jié)點(diǎn)開始，和左右節(jié)點(diǎn)中最小值進(jìn)行交換，如此循環(huán)至底部。

至此，思路講解完畢，下面是完整代碼。