堆（Heap）是計算機科學(xué)中的一種特別的完全二叉樹結(jié)構(gòu)，它滿足某種特定順序，用于實現(xiàn)優(yōu)先隊列等數(shù)據(jù)結(jié)構(gòu)。堆主要有兩種類型：最大堆（Max Heap）和最小堆（Min Heap）。

定義

• 最大堆：在最大堆中，任何一個父節(jié)點的值都大于或等于它的子節(jié)點的值。這意味著堆的根節(jié)點包含了堆中的最大值。
• 最小堆：在最小堆中，任何一個父節(jié)點的值都小于或等于它的子節(jié)點的值。這意味著堆的根節(jié)點包含了堆中的最小值。

特性

1. 完全二叉樹：堆是一種特殊的完全二叉樹，除了最后一層外，其他每一層都被完全填充，并且所有節(jié)點都盡可能地向左對齊。
2. 堆性質(zhì)：堆中的每個節(jié)點都滿足子節(jié)點小于（最大堆）或大于（最小堆）父節(jié)點的性質(zhì)。

表示

堆通常使用數(shù)組來表示。對于給定位置的元素i（從0開始計數(shù)）：

• 它的父節(jié)點位置是 (i - 1) / 2。
• 它的左子節(jié)點位置是 2*i + 1。
• 它的右子節(jié)點位置是 2*i + 2。

操作

• 插入（Insert）：在堆中插入一個新元素。新元素被加到堆的末尾，然后通過一系列上浮（對于最大堆）或下沉（對于最小堆）操作，恢復(fù)堆的性質(zhì)。
• 刪除（Delete）：在最大堆中刪除根節(jié)點（即最大元素），在最小堆中刪除根節(jié)點（即最小元素）。通常，堆的最后一個元素被移動到根節(jié)點，然后通過一系列下沉操作，恢復(fù)堆的性質(zhì)。
• 構(gòu)建（Build）：將一個無序數(shù)組構(gòu)建成一個堆?？梢酝ㄟ^從最后一個非葉子節(jié)點開始，向前進行下沉操作，直到根節(jié)點，來實現(xiàn)。

應(yīng)用

• 優(yōu)先隊列：堆是實現(xiàn)優(yōu)先隊列的理想結(jié)構(gòu)，可以快速訪問隊列中的最大值或最小值。
• 堆排序：堆排序算法是基于堆的選擇排序，通過構(gòu)建最大堆或最小堆，來實現(xiàn)數(shù)組的排序。
• 圖算法：在Dijkstra和Prim算法中，堆用于高效地選取最小邊或最短路徑。

堆結(jié)合了二叉樹的結(jié)構(gòu)特點和數(shù)組的簡單性，提供了一種高效的方式來實現(xiàn)動態(tài)排序和優(yōu)先級隊列管理。