一、定義

二叉堆本質上是一種完全二叉樹，它分為兩個類型。

1. 大頂堆(最大堆)

最大堆的任何一個父節點的值，都大于或等于它左、右孩子節點的值

2. 小頂堆(最小堆)

最小堆的任何一個父節點的值，都小于或等于它左、右孩子節點的值

二叉堆的根節點叫作堆頂。

最大堆和最小堆的特點決定了：最大堆的堆頂是整個堆中的最大元素；最小堆的堆頂是整個堆中的最小元素

二、二叉堆存儲

完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。

因為我們不需要 存儲左右子節點的指針，單純地通過數組的下標，就可以找到一個節點的左右子節點和父節點。

從圖中我們可以看到，數組中下標為 i 的節點的左子節點，就是下標為 i?2 的節點，右子節點就是下標 為 i?2+1 的節點，父節點就是下標為 i/2 取整的節點。

三、二叉堆的典型應用

優先隊列

利用堆求 Top K問題

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