一、定義

二叉堆本質(zhì)上是一種完全二叉樹，它分為兩個(gè)類型。

1. 大頂堆(最大堆)

最大堆的任何一個(gè)父節(jié)點(diǎn)的值，都大于或等于它左、右孩子節(jié)點(diǎn)的值

2. 小頂堆(最小堆)

最小堆的任何一個(gè)父節(jié)點(diǎn)的值，都小于或等于它左、右孩子節(jié)點(diǎn)的值

二叉堆的根節(jié)點(diǎn)叫作堆頂。

最大堆和最小堆的特點(diǎn)決定了：最大堆的堆頂是整個(gè)堆中的最大元素；最小堆的堆頂是整個(gè)堆中的最小元素

二、二叉堆存儲(chǔ)

完全二叉樹比較適合用數(shù)組來存儲(chǔ)。用數(shù)組來存儲(chǔ)完全二叉樹是非常節(jié)省存儲(chǔ)空間的。

因?yàn)槲覀儾恍枰?存儲(chǔ)左右子節(jié)點(diǎn)的指針，單純地通過數(shù)組的下標(biāo)，就可以找到一個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)和父節(jié)點(diǎn)。

從圖中我們可以看到，數(shù)組中下標(biāo)為 i 的節(jié)點(diǎn)的左子節(jié)點(diǎn)，就是下標(biāo)為 i?2 的節(jié)點(diǎn)，右子節(jié)點(diǎn)就是下標(biāo) 為 i?2+1 的節(jié)點(diǎn)，父節(jié)點(diǎn)就是下標(biāo)為 i/2 取整的節(jié)點(diǎn)。

三、二叉堆的典型應(yīng)用

優(yōu)先隊(duì)列

利用堆求 Top K問題

在一個(gè)包含 n 個(gè)數(shù)據(jù)的數(shù)組中，我們可以維護(hù)一個(gè)大小為 K 的小頂堆，順序遍歷數(shù)組，從數(shù)組中取出數(shù) 據(jù)與堆頂元素比較。如果比堆頂元素大，我們就把堆頂元素刪除，并且將這個(gè)元素插入到堆中；如果比 堆頂元素小，則不做處理，繼續(xù)遍歷數(shù)組。這樣等數(shù)組中的數(shù)據(jù)都遍歷完之后，堆中的數(shù)據(jù)就是前 K 大 數(shù)據(jù)了