堆是優先權清單的更有效率版本。考慮到Priority Queue Sorted 和Unsorted 的插入和移除方法，Unsorted 的插入成本為O(1)，移除成本為O(n)，而Sorted 的插入成本為O(n)，移除成本為O( 1)。
| sorted | unsorted | |
|---|---|---|
| insert | O(n) | O(1) |
| remove | O(1) | O(n) |
堆是由陣列建構的，但它的表示是一棵二元樹，優先順序最高的元素位於頂部，即根。從上到下、從右到左都塞滿了，沒有一個小孩漏掉！
？
但是，有可能建立由最高鍵值定義的最高優先權的資料結構。在這種情況下，我們有最大堆，我們稍後會看到。
最小堆
要成為有效的堆，所有子元素的優先權必須低於或等於其父元素。此外，它必須是完整的，不能缺少子元素，否則數組將有空格。
？
執行此定義的更正式方法是，如果二元樹的等級0、1、2、···h − 1 具有最大可能元素並且分配了等級h 中存在的元素，則二元樹是完整的盡可能靠左。
如上所述，堆由數組組成（以綠色表示），但可以將其視為樹結構，如下圖所示。
組裝Heap有兩種方法，第一個元素位於位置0，或不位於位置0，在本文中我們將看到兩種情況之間的差異。頂部的元素總是有它們的子元素，通常稱為底部的元素，要發現這些子元素，在索引為 0 的情況下，您可以使用以下計算來獲得此資訊：
rigthChild = LeftChild + 1 //para saber o elemento da esquerda do pai leftChild = indexDoFilho * 2 +1 //para saber qual o pai do elemento parent = (indexDoFilho -1)/2
如果使用不填0的版本，只需減少總和即可，即1-1=0，在父情況下是index / 2。
它總是添加在末尾，您唯一應該關心的是檢查子元素是否具有比父元素更低的鍵，為此目的會執行冒泡，即插入元素的鍵為和父親相比，必要時改變。
更詳細地說，將元素放置在樹的最後一個空白空間中，因為您需要將其鍵與父元素的鍵進行比較，所以我們需要計算父元素的索引以存取其鍵。要找出父親，請使用提到的計算：
parent = (indexDoFilho -1)/2
為此，indexDoFilho丟失了：為了獲得它，我們將一個變數作為當前索引，因為我們在插入中是最後一個添加，當前索引是最後一個，是：
currentIndex = size-1
現在有了當前索引，呼叫 Parent 並找出正在插入的元素的父元素。我們需要這個新元素的父元素，因為為了正確組織樹，必須將該元素與其父元素進行比較，如果其鍵較小，則它們必須交換位置。
只要當前索引大於0（為了避免拾取不可用的索引）並且當前索引小於父級索引，如果這個條件成立，則需要與父級交換該元素以保證最小堆的所有權，然後發生交換，然後目前索引接收父級的索引，然後將父級的父級（KKKKK）取為。 Swap 是一種使用正常交換值的結構的方法。
rigthChild = LeftChild + 1 //para saber o elemento da esquerda do pai leftChild = indexDoFilho * 2 +1 //para saber qual o pai do elemento parent = (indexDoFilho -1)/2
有關聯：
parent = (indexDoFilho -1)/2
交換是交換值的正常方法：
currentIndex = size-1
如果目前（子）元素的值小於父元素的值，則表示違反了最小堆屬性。在最小堆中，父堆必須永遠小於或等於子堆。 當不滿足此條件時，子級必須與父級交換位置，以便較小的值繼續在堆中“爬升”，直到找到正確的位置，在該位置將維護屬性。
刪除索引 0 的元素，但樹不再完整！要解決這個問題，請將陣列的最後一個元素拉到開頭，即新增的最後一個元素位於樹的頂部。之後，再次檢查，但現在是從上到下。換句話說，現在是父母和孩子比較的時候了！ （下沉）
sinkDown() 方法將元素在堆中向下移動（或“下沉”），直到它位於正確的位置，其中它的值小於或等於其子元素的值（如果它位於有子元素的位置） .
在sinkDown中，有一個變數用於儲存從根開始的最低鍵的元素的索引，另一個變數用於儲存當前索引。然後，循環將持續到當前元素的索引等於具有最低鍵的元素的索引。在循環內部，取得目前的子級，並查看子級是否在數組範圍內，如果子級索引小於最小索引，則更新最小值。
public void insert(K key, V value) { //o(log n)
if (isFull()){
throw new RuntimeException("full");
}
//adc a entry na ultima posição do vetor
heap[size++]=new PriorityEntry(key, value);
//guarda o index que esse novo elemento tá
int currentIndex = size-1;
//chama o método parent pra calcular quem é o pai do novo elemento
int parent = parent(currentIndex);
//percorre enquanto o index nao for o 0 e o index ser
while (currentIndex>0 && compare(currentIndex, parent)<0){
swap(currentIndex, parent);
currentIndex = parent;
parent = parent(currentIndex);
}
}
在這種情況下：
protected int parent(int index){
return (index-1)/2;
}
最小堆屬性：
計算孩子和父母的位置：
沒有索引 0 的版本： 只要從計算中減去 1，結果是：
最高值位於根節點，因此父節點的值與其子節點相同或更大
孩子和家長的計算公式：
在末尾添加元素並向上冒泡，這會將元素與其父元素進行比較，並在必要時更改位置。 O(log n)。
rigthChild = LeftChild + 1 //para saber o elemento da esquerda do pai leftChild = indexDoFilho * 2 +1 //para saber qual o pai do elemento parent = (indexDoFilho -1)/2
刪除heapMax[0]元素，也就是根，然後取出最後一個元素並將其向上移動到根，調用sinkdown，然後將新元素從根向下推，直到找到正確的位置。
sinkDown需要確保父節點中的值大於等於子節點中的值。因此，當下沉一個節點時，它將與最大子節點進行比較。
在最小堆中，sinkDown必須確保父節點中的值小於或等於子節點的值。在本例中，將與最小的孩子進行比較。
parent = (indexDoFilho -1)/2
currentIndex = size-1
以上是堆 - 最小和最大的詳細內容。更多資訊請關注PHP中文網其他相關文章！
