Heap – Min. und Max

Heap – Min. Heap

Heap ist eine effizientere Version der Prioritätenliste. Berücksichtigen Sie die Einfügungs- und Entfernungsmethoden der Prioritätswarteschlange Sortiert und Unsortiert, wobei das unsortierte Einfügen O(1) kostet, das Entfernen O(n), während das sortierte Einfügen O(n) kostet und das Entfernen O(1).

	sorted	unsorted
insert	O(n)	O(1)
remove	O(1)	O(n)

Heap wird durch ein Array erstellt, aber seine Darstellung ist ein Binärbaum. Das Element mit der höchsten Priorität befindet sich oben, die Wurzel. Es ist von oben nach unten und von rechts nach links gefüllt, ohne dass Kinder fehlen!

?

Es besteht jedoch die Möglichkeit, die Datenstruktur mit der höchsten Priorität aufzubauen, die durch den höchsten Schlüsselwert definiert wird. In diesem Fall haben wir den maximalen Heap, den wir später sehen werden.

Min_Heap

Um ein gültiger Heap zu sein, müssen alle untergeordneten Elemente eine niedrigere oder gleiche Priorität haben wie ihre Eltern. Darüber hinaus muss es vollständig sein und darf keine untergeordneten Elemente enthalten, andernfalls enthält das Array ein Leerzeichen.

?

Eine formellere Art, diese Definition auszuführen, besteht darin, zu sagen, dass ein Binärbaum vollständig ist, wenn seine Ebenen 0, 1, 2, · · · h − 1 die maximal möglichen Elemente aufweisen und die auf Ebene h vorhandenen Elemente zugeordnet sind so weit links wie möglich.

Wie bereits erwähnt, besteht der Heap aus einem Array (dargestellt in Grün), kann aber als Baumstruktur betrachtet werden, wie im Bild unten gezeigt.

Es gibt zwei Möglichkeiten, den Heap zusammenzustellen: mit dem ersten Element an Position 0 oder ohne Position 0. In diesem Artikel werden wir den Unterschied zwischen den beiden Fällen sehen. Die Elemente oben haben immer ihre untergeordneten Elemente, die allgemein als Elemente unten bezeichnet werden. Um diese untergeordneten Elemente zu ermitteln, können Sie diese Informationen im Fall von Index 0 mithilfe dieser Berechnungen erhalten:

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

Wenn Sie eine Version verwenden, bei der 0 nicht ausgefüllt ist, reduzieren Sie einfach die Summe, d. h. 1-1=0, im übergeordneten Fall ist es Index / 2.

Einfügen

Es wird immer am Ende hinzugefügt. Die einzige Sorge, die Sie haben sollten, besteht darin, zu prüfen, ob das untergeordnete Element einen niedrigeren Schlüssel als das übergeordnete Element hat. Zu diesem Zweck wird ein Bubbling-Up durchgeführt, bei dem die Schlüssel des eingefügten Elements vorliegen verglichen und der Vater, bei Bedarf ändern.

Genauer gesagt: Platzieren Sie das Element im letzten leeren Bereich des Baums. Da Sie seinen Schlüssel mit dem des übergeordneten Elements vergleichen müssen, müssen wir den Index des übergeordneten Elements berechnen, um auf seinen Schlüssel zuzugreifen. Um den Vater herauszufinden, verwenden Sie die genannte Berechnung:

parent = (indexDoFilho -1)/2

Und dafür fehlt der IndexDoFilho: Um dies zu erhalten, nehmen wir eine Variable als aktuellen Index, da wir uns in der Einfügung befinden, die eine Addition am Ende ist, ist der aktuelle Index der letzte, nämlich:

currentIndex = size-1

Wenn Sie nun über den aktuellen Index verfügen, rufen Sie „Parent“ auf und finden Sie heraus, wer der Vater des einzufügenden Elements ist. Wir wollen das übergeordnete Element dieses neuen Elements, denn um den Baum richtig zu organisieren, muss dieses Element mit seinem übergeordneten Element verglichen werden und, wenn sein Schlüssel kleiner ist, müssen sie die Positionen tauschen.

Solange der aktuelle Index größer als 0 ist (um zu vermeiden, dass ein nicht verfügbarer Index erfasst wird) und der aktuelle Index kleiner als der Index des übergeordneten Elements ist, muss das Element mit dem übergeordneten Element ausgetauscht werden, wenn diese Bedingung zutrifft um den Besitz des Mindestheaps zu garantieren, und dann erfolgt der Austausch und dann empfängt der aktuelle Index den Index des übergeordneten Elements und übernimmt dann den übergeordneten Index des übergeordneten Elements (KKKKK) für . Swap ist eine Methode, die die Struktur eines normalen Werteaustauschs nutzt.

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

Verwandt sein:

parent = (indexDoFilho -1)/2

Swap ist eine normale Methode zum Austausch von Werten:

currentIndex = size-1

Wenn der Wert des aktuellen (untergeordneten) Elements kleiner als der Wert des übergeordneten Elements ist, weist dies darauf hin, dass die Eigenschaft des minimalen Heapspeichers verletzt wurde. In einem minimalen Heap muss der übergeordnete Heap immer kleiner oder gleich dem untergeordneten Heap sein. Wenn diese Bedingung nicht erfüllt ist, muss das Kind die Plätze mit dem Elternteil tauschen, damit der kleinere Wert im Heap weiter „aufsteigt“, bis er die richtige Position findet, an der die Eigenschaft beibehalten wird.

Entfernen

Entfernt das Index-0-Element, aber der Baum ist nicht mehr vollständig! Um dieses Problem zu lösen, ziehen Sie das letzte Element des Arrays an den Anfang, d. h. das zuletzt hinzugefügte Element wird an die Spitze des Baums verschoben. Überprüfen Sie danach noch einmal, aber jetzt von oben nach unten. Mit anderen Worten: Jetzt ist es an der Zeit, Eltern mit ihren Kindern zu vergleichen! (sinkt)
Die sinkDown()-Methode verschiebt das Element im Heap nach unten (oder „sinkt“), bis es sich an der richtigen Position befindet, an der sein Wert kleiner oder gleich dem seiner untergeordneten Elemente ist (wenn es sich an einer Position mit untergeordneten Elementen befindet). .
In sinkDown gibt es eine Variable zum Speichern des Index des Elements mit dem niedrigsten Schlüssel beginnend bei der Wurzel und eine weitere für den aktuellen Index. Dann folgt eine Schleife, die so lange dauert, bis der Index des aktuellen Elements dem Index des Elements mit dem niedrigsten Schlüssel entspricht. Rufen Sie innerhalb der Schleife die untergeordneten Elemente des aktuellen ab und prüfen Sie, ob sich die untergeordneten Elemente innerhalb des Array-Bereichs befinden. Wenn der Index des untergeordneten Elements kleiner als der Mindestindex ist, wird der Mindestindex aktualisiert.

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);
    }
}

In diesem Fall:

protected int parent(int index){
        return (index-1)/2;
}

Zusammenfassung:

Min. Heap-Eigenschaften:

• Vollständige binäre Baumstruktur.
• Der übergeordnete Knoten hat immer einen Wert, der gleich oder kleiner als der seiner untergeordneten Knoten ist.
• Implementiert über ein Array, wobei die Position der untergeordneten und übergeordneten Elemente durch Formeln basierend auf dem Index bestimmt wird.

So berechnen Sie die Positionen von Kindern und Eltern:

• Left: leftChild = index * 2 1
• Rechts: rightChild = index * 2 2
• Übergeordnetes Element: übergeordnetes Element = (Index - 1) / 2

Version ohne Index 0: Subtrahieren Sie einfach 1 von den Berechnungen, was zu Folgendem führt:

• leftChild = index * 2
• rightChild = index * 2 1
• parent = index / 2

Heap – Max. Heap

Der höchste Wert liegt an der Wurzel, sodass der übergeordnete Knoten den gleichen oder einen größeren Wert hat als seine untergeordneten Knoten

Die Formeln zur Berechnung von Kindern und Eltern:

• Left: leftChild = index * 2 1
• Rechts: rightChild = index * 2 2
• Übergeordnetes Element: übergeordnetes Element = (Index - 1) / 2

Einfügen

Fügt das Element am Ende hinzu und sprudelt nach oben, wodurch das Element mit seinem übergeordneten Element verglichen und bei Bedarf die Position geändert wird. 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

Entfernen

Entfernt das heapMax[0]-Element, auch bekannt als die Wurzel, und verschiebt dann das letzte Element nach oben zur Wurzel, ruft sinkdown auf und schiebt dann das neue Element von der Wurzel nach unten, bis es seine richtige Position findet.

sinkDown muss sicherstellen, dass der Wert im übergeordneten Knoten größer oder gleich den Werten in den untergeordneten Knoten ist. Wenn ein Knoten versenkt wird, wird er daher mit dem größten untergeordneten Knoten verglichen.

Im Min Heap muss sinkDown sicherstellen, dass der Wert im übergeordneten Knoten kleiner oder gleich den Werten der untergeordneten Knoten ist. In diesem Fall erfolgt der Vergleich mit dem kleinsten Kind.

parent = (indexDoFilho -1)/2

currentIndex = size-1

Unterschiede

• In Max Heap muss sinkDown sicherstellen, dass der Wert im übergeordneten Knoten größer oder gleich den Werten in den untergeordneten Knoten ist. Wenn ein Knoten versenkt wird, wird er daher mit dem größten untergeordneten Knoten verglichen.
• Wenn in Max Heap der übergeordnete Knoten kleiner als der größte seiner untergeordneten Knoten ist, muss er mit dem größten untergeordneten Knoten ausgetauscht werden, um sicherzustellen, dass der größte Wert so hoch wie möglich ist.
• Im Min Heap muss sinkDown sicherstellen, dass der Wert im übergeordneten Knoten kleiner oder gleich den Werten der untergeordneten Knoten ist. In diesem Fall erfolgt der Vergleich mit dem kleinsten Kind.
• Im Min Heap erfolgt die Umschaltung, wenn der übergeordnete Knoten größer als der kleinste der untergeordneten Knoten ist, wobei der kleinste Wert oben bleibt

Das obige ist der detaillierte Inhalt vonHeap – Min. und Max. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!