堆 - 最小和最大

堆 - 最小堆

堆是優先權清單的更有效率版本。考慮到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;
}

概括：

最小堆屬性：

• 完整的二元樹結構。
• 父節點的值總是等於或小於其子節點。
• 透過數組實現，其中子級和父級的位置由基於索引的公式決定。

計算孩子和父母的位置：

• 左: leftChild = 索引 * 2 1
• 右: rightChild = 索引 * 2 2
• 父級：父級 = (索引 - 1) / 2

沒有索引 0 的版本： 只要從計算中減去 1，結果是：

• leftChild = 索引 * 2
• rightChild = 索引 * 2 1
• 父級 = 索引 / 2

堆 - 最大堆

最高值位於根節點，因此父節點的值與其子節點相同或更大

孩子和家長的計算公式：

• 左: leftChild = 索引 * 2 1
• 右: rightChild = 索引 * 2 2
• 父級：父級 = (索引 - 1) / 2

插入

在末尾添加元素並向上冒泡，這會將元素與其父元素進行比較，並在必要時更改位置。 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

差異

• 在Max Heap中，sinkDown需要保證父節點中的值大於或等於子節點中的值。因此，當下沉一個節點時，它將與最大子節點進行比較。
• 在Max Heap中，如果父節點小於其子節點中最大的節點，那麼它必須與最大的子節點交換，以確保最大值盡可能高。
• 在最小堆中，sinkDown必須確保父節點中的值小於或等於子節點的值。在本例中，將與最小的孩子進行比較。
• 在最小堆中，如果父節點大於子節點中最小的節點，就會發生切換，將最小值保留在頂部

以上是堆 - 最小和最大的詳細內容。更多資訊請關注PHP中文網其他相關文章！