Algorithmen lernen

Kapitel 4. Aufhäufen

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

In diesem Kapitel lernst du:

• Die Datentypen Warteschlange und Prioritätswarteschlange.

• Die binäre Datenstruktur des Heaps, die 1964 erfunden wurde und in einem Array gespeichert werden kann.

• Dass in einem max binary heap ein Eintrag mit einer höheren numerischen Priorität eine höhere Priorität hat als ein Eintrag mit einer kleineren numerischen Priorität. In einem min binary heap haben Einträge mit einer kleineren numerischen Priorität eine höhere Priorität.

• Wie man einen Eintrag (Wert, Priorität) in einem binären Heap in O(log N) einreiht, wobei N die Anzahl der Einträge im Heap ist.

• Wie findet man den Wert mit der höchsten Priorität in einem binären Heap in O(1).

• Wie man den Wert mit der höchsten Priorität aus einem binären Heap in O(log N) entfernt.

Wie wäre es, wenn du statt einer Sammlung von Werten eine Sammlung von Einträgen speicherst, wobei jeder Eintrag einen Wert und eine damit verbundenePriorität in Form einer Zahl hat? Bei zwei Einträgen ist derjenige wichtiger als der andere, dessen Priorität höher ist. Die Herausforderung besteht nun darin, neue Einträge (Wert, Priorität) in eine Sammlung einzufügen und den Wert des Eintrags mit der höchsten Priorität aus der Sammlung zu entfernen und zurückzugeben.

Dieses Verhalten definiert eine Prioritäts-Warteschlange - einenDatentyp, der enqueue(value, priority) und dequeue() effizient unterstützt und den Wert mit der höchsten Priorität entfernt. Die Prioritätswarteschlange unterscheidet sich von der im vorherigen Kapitel besprochenen Symboltabelle, weil du die Priorität nicht im Voraus kennen musst, wenn du den Wert mit der höchsten Priorität entfernen willst.

Wenn ein belebter Nachtclub zu voll wird, bildet sich draußen eine Schlange von Menschen, wie in Abbildung 4-1 dargestellt. Wenn mehr Menschen versuchen, den Club zu betreten, müssen sie am Ende der Schlange warten. Die erste Person, die den Nachtclub aus der Schlange heraus betritt, ist diejenige, die am längsten gewartet hat. Dieses Verhalten stellt den wesentlichen abstrakten Datentyp derWarteschlange dar, mit einer enqueue(value) Operation, dievalue zum neuesten Wert am Ende der Warteschlange hinzufügt unddequeue() den ältesten in der Warteschlange verbleibenden value entfernt. Eine andere Möglichkeit, diese Erfahrung zu beschreiben, ist "First in, first out" (FIFO), was so viel bedeutet wie "Wer zuerst in der Warteschlange ist, wird auch zuerst aus der Warteschlange genommen".

Abbildung 4-1. Warten in einer Warteschlange in einem Nachtclub

Im vorigen Kapitel habe ich die Datenstruktur der verketteten Liste beschrieben, die ich wieder mit einer Node verwenden werde, die eine value für die Warteschlange speichert:

class Node:
  def __init__(self, val):
    self.value = val
    self.next = None

Unter Verwendung dieser Struktur verfügt die Queue Implementierung inListing 4-1 über eine enqueue() Operation, um einen Wert an das Ende einer verknüpften Liste anzuhängen. Abbildung 4-2 zeigt das Ergebnis der Einreihung (in dieser Reihenfolge) von "Joe", "Jane" und "Jim" in eine Nachtclub-Warteschlange.

"Joe" wird als erster aus der Warteschlange genommen, wodurch eine Warteschlange mit zwei Personen entsteht, in der Jane" die erste Person in der Schlange bleibt.

In Queue werden die Operationen enqueue() und dequeue() in konstanter Zeit ausgeführt, unabhängig von der Gesamtzahl der Werte in der Warteschlange.

Abbildung 4-2. Modellierung einer Nachtclub-Warteschlange mit drei Knotenpunkten

Listing 4-1. Implementierung einer verketteten Liste des Datentyps Queue

class Queue:
  def __init__(self):
    self.first = None                     
    self.last = None

  def is_empty(self):
    return self.first is None             

  def enqueue(self, val):
    if self.first is None:                
      self.first = self.last = Node(val)
    else:
      self.last.next = Node(val)          
      self.last = self.last.next

  def dequeue(self):
    if self.is_empty():
      raise RuntimeError('Queue is empty')

    val = self.first.value                
    self.first = self.first.next          
    return val

Zu Beginn sind first und last None .

Ein Queue ist leer, wenn first None ist.

Wenn Queue leer ist, setze first und last auf die neu erstellte Node.

Wenn Queue nicht leer ist, füge nach last hinzu und passe last so an, dass es auf das neu erstellte Node zeigt.

first verweist auf den Node Wert, der zurückgegeben werden soll.

Setze first auf den zweiten Node in der Liste, falls er existiert.

Ändern wir die Situation: Der Nachtclub beschließt, seinen Gästen zu erlauben, einen beliebigen Geldbetrag auszugeben, um einen speziellen Pass zu kaufen, der den Gesamtbetrag der Ausgaben aufzeichnet. Ein Gast könnte zum Beispiel einen 50-Dollar-Pass kaufen, während ein anderer einen 100-Dollar-Pass kauft. Wenn der Club zu voll wird, stellen sich die Leute in die Schlange, um zu warten. Die erste Person, die den Nachtclub aus der Schlange heraus betritt, ist jedoch diejenige, die einen Pass mit dem höchsten Zahlungsbetrag von allen in der Schlange hat. Wenn zwei oder mehr Personen in der Schlange das meiste Geld ausgegeben haben, wird einer von ihnen ausgewählt, um den Nachtclub zu betreten. Gäste ohne Ausweis werden so behandelt, als hätten sie 0 $ bezahlt.

In Abbildung 4-3 betritt der Gast in der Mitte mit einem 100-Dollar-Pass als Erster den Club, gefolgt von den beiden 50-Dollar-Gästen (in einer bestimmten Reihenfolge). Alle anderen Gäste, die keine Eintrittskarte haben, werden als gleichwertig betrachtet, sodass jeder von ihnen als Nächster den Club betreten kann.

Abbildung 4-3. Mit dem gekauften Pass können die Besucher schneller vorankommen

Hinweis

Ein Prioritätswarteschlangen-Datentyp legt nicht fest , was zu tun ist, wenn zwei oder mehr Werte die gleiche höchste Priorität haben. Je nach Implementierung kann es sogar sein, dass die Prioritätswarteschlange die Werte nicht in der Reihenfolge zurückgibt, in der sie in die Warteschlange gestellt wurden. Eine Heap-basierte Prioritätswarteschlange - wie in diesem Kapitel beschrieben - gibt Werte mit gleicher Priorität nicht in der Reihenfolge zurück, in der sie in die Warteschlange gestellt wurden. Das integrierte Modul heapq implementiert eine Prioritätswarteschlange mit einem Heap, den ich in Kapitel 8 behandle.

Dieses überarbeitete Verhalten definiert den abstrakten Datentyp der Prioritätswarteschlange; allerdings können enqueue() und dequeue() nicht mehr effizient in konstanter Zeit implementiert werden. Wenn du eine Datenstruktur mit verketteten Listen verwendest, ist enqueue() zwar immer noch O(1), aber dequeue() muss möglicherweise alle Werte in der Prioritätswarteschlange überprüfen, um den Wert mit der höchsten Priorität zu finden, was im schlimmsten Fall O(N) erfordert. Wenn du dagegen alle Elemente nach Priorität sortiert aufbewahrst, benötigt dequeue()O(1), aber jetzt benötigt enqueue() im schlimmsten Fall O(N), um herauszufinden, wo der neue Wert eingefügt werden soll.

Nach unseren bisherigen Erfahrungen gibt es fünf mögliche Strukturen, die alle ein Entry Objekt verwenden, um einen Eintrag (Wert, Priorität) zu speichern:

Array

Ein Array mit ungeordneten Einträgen, das keine Struktur hat und auf das Beste hofft. enqueue() ist eine Operation mit konstanter Zeit, aber dequeue() muss das gesamte Array nach dem Wert mit der höchsten Priorität durchsuchen, um ihn zu entfernen und zurückzugeben. Da das Array eine feste Größe hat, könnte diese Prioritätswarteschlange voll werden.

Eingebaut

Eine ungeordnete Liste, die mit den in Python integrierten Operationen bearbeitet wird und eine ähnliche Leistung wie Array bietet.

BestellungA

Ein Array mit Einträgen, die nach steigender Priorität sortiert sind. Aufenqueue() kannst du die Variante der binären Array-Suche (sieheListing 2-4) verwenden, um herauszufinden, wo der Eintrag platziert werden soll, und die Array-Einträge manuell verschieben, um Platz zu schaffen. dequeue() ist zeitunabhängig, da die Einträge vollständig geordnet sind und der Eintrag mit der höchsten Priorität am Ende des Arrays gefunden wird. Da das Array eine feste Größe hat, könnte diese Prioritätswarteschlange voll werden.

Verknüpft

Eine verknüpfte Liste von Einträgen, deren erster Eintrag die höchste Priorität aller Einträge in der Liste hat; jeder nachfolgende Eintrag ist kleiner oder gleich dem vorherigen Eintrag. Diese Implementierung reiht neue Werte an der richtigen Stelle in der verknüpften Liste ein, damit dequeue() eine Operation mit konstanter Zeit ist.

BestellungL

Eine Python-Liste mit aufsteigenden Einträgen nach steigender Priorität. Aufenqueue() fügst du mit der Binary Array Search-Variante den Eintrag dynamisch an der richtigen Stelle ein. dequeue() ist zeitlich konstant, da der Eintrag mit der höchsten Priorität immer am Ende der Liste steht.

Um diese Implementierungen zu vergleichen, habe ich ein Experiment entwickelt, bei dem 3N/2 enqueue() Operationen und 3N/2 dequeue()Operationen sicher ausgeführt werden. Für jede Implementierung messe ich die Gesamtausführungszeit und teile sie durch 3N, um die durchschnittlichen Operationskosten zu berechnen. Wie ausTabelle 4-1 hervorgeht, ist ein Array mit fester Größe am langsamsten, während integrierte Python-Listen die Zeit halbieren. Ein Array mit sortierten Einträgen halbiert die Zeit noch einmal und eine verknüpfte Liste verbessert sich um weitere 20%. Der eindeutige Sieger ist jedoch OrderL.

Tabelle 4-1. Durchschnittliche Operationsleistung (Zeit in ns) bei Probleminstanzen der Größe N

N	Heap	BestellungL	Verknüpft	BestellungA	Eingebaut	Array
256	6.4	2.5	3.9	6.0	8.1	13.8
512	7.3	2.8	6.4	9.5	14.9	26.4
1,024	7.9	3.4	12.0	17.8	28.5	52.9
2,048	8.7	4.1	23.2	33.7	57.4	107.7
4,096	9.6	5.3	46.6	65.1	117.5	220.3
8,192	10.1	7.4	95.7	128.4	235.8	446.6
16,384	10.9	11.7	196.4	255.4	470.4	899.9
32,768	11.5	20.3	—	—	—	—
65,536	12.4	36.8	—	—	—	—

Bei diesen Ansätzen steigen die durchschnittlichen Kosten einer enqueue() oder dequeue()Operation direkt proportional zu N. Die Spalte mit der Bezeichnung "Heap" inTabelle 4-1 zeigt jedoch die Leistungsergebnisse bei Verwendung einerHeap Datenstruktur; ihre durchschnittlichen Kosten steigen direkt proportional zulog(N), wie du in Abbildung 4-4 sehen kannst, und sie übertrifft die Implementierung mit geordneten Python-Listen deutlich. Du weißt, dass die Leistung logarithmisch ist, wenn die Laufzeitleistung nur dann konstant ansteigt, wenn sich die Problemgröße verdoppelt. InTabelle 4-1 steigt die Laufzeit bei jeder Verdopplung um etwa 0,8 Nanosekunden.

Die 1964 erfundene Datenstruktur Heap bietet O(log N) Leistung für die Operationen einer Prioritätswarteschlange. Im weiteren Verlauf dieses Kapitels geht es nicht um die Werte, die in einer Warteschlange stehen - es können Strings, numerische Werte oder sogar Bilddaten sein, wen interessiert das schon? Mir geht es nur um die numerische Priorität für jeden Eintrag. In den übrigen Abbildungen in diesem Kapitel werden nur die Prioritäten der Einträge gezeigt, die in die Warteschlange gestellt wurden. Bei zwei Einträgen in einem Max Heap hat derjenige, dessen Priorität einen größeren Wert hat, die höhere Priorität.

Ein Heap hat eine maximale Größe M - die im Voraus bekannt ist - und kann N < M Einträge speichern. Ich erkläre jetzt die Struktur eines Heaps, zeige, wie er im Laufe der Zeit innerhalb seiner maximalen Größe wachsen und schrumpfen kann, und zeige, wie ein gewöhnliches Array seine N Einträge speichert.

Abbildung 4-4. O(log N) Verhalten von Heap übertrifft O(N) Verhalten für andere Ansätze

Max Binary Heaps

Es mag wie eine seltsame Idee erscheinen, aber was ist, wenn ich die Einträge nur "teilweise sortiere"? Abbildung 4-5 zeigt einen Max Heap mit 17 Einträgen; für jeden Eintrag wird nur seine Priorität angezeigt. Wie du sehen kannst, enthält die Ebene 0 einen einzigen Eintrag, der die höchste Priorität aller Einträge im Max Heap hat. Am Pfeil x → y kannst du sehen, dass die Priorität des Eintrags x ≥ der Priorität des Eintrags y ist.

Abbildung 4-5. Ein Beispiel für einen max binary heap

Diese Einträge sind nicht vollständig geordnet, wie es bei einer sortierten Liste der Fall wäre. Du musst also eine Weile suchen, um den Eintrag mit der niedrigsten Priorität zu finden (Hinweis: Er befindet sich auf Ebene 3). Aber die resultierende Struktur hat ein paar nette Eigenschaften: Es gibt zwei Einträge auf Ebene 1, von denen einer die zweithöchste Priorität haben muss (oder mit dem höchsten gleichgestellt ist, richtig?). Jede Ebene k- außerder letzten - ist voll und enthält 2^k Einträge. Nur die unterste Ebene ist teilweise gefüllt (d.h. sie hat 2 von 16 möglichen Einträgen), und sie wird von links nach rechts gefüllt. Du kannst auch sehen, dass die gleiche Priorität im Heap vorkommen kann - die Prioritäten 8 und 14 tauchen mehrfach auf.

Von jedem Eintrag gehen nicht mehr als 2 Pfeile aus, so dass es sich um einenmaximal binären Heap handelt. Nehmen wir den Eintrag auf Ebene 0, dessen Priorität 15 ist: Der erste Eintrag auf Ebene 1 mit Priorität 13 ist sein linkes Kind; der zweite Eintrag auf Ebene 1 mit Priorität 14 ist sein rechtes Kind. Der Eintrag mit der Priorität 15 ist der Elternteil der beiden Kindeinträge auf Ebene 1.

Im Folgenden werden die Eigenschaften eines max binary heap zusammengefasst:

Heap-geordnetes Eigentum

Die Priorität eines Eintrags ist größer als oder gleich der Priorität seines linken und seines rechten Untereintrags (falls vorhanden). Die Priorität jedes Eintrags (mit Ausnahme des obersten) ist kleiner oder gleich der Priorität seines übergeordneten Eintrags.

Eigenschaft der Heap-Form

Jede Ebene k muss mit 2 Einträgen gefüllt werden^k Einträge gefüllt werden (von links nach rechts), bevor ein Eintrag auf der Ebene k + 1 erscheint.

Wenn ein binärer Heap nur einen einzigen Eintrag enthält, gibt es nur eine einzige Ebene, nämlich 0, weil²⁰ = 1 ist. Wie viele Ebenen werden für einen binären Heap benötigt, um N > 0 Einträge zu speichern? Mathematisch gesehen muss ich eine Formel definieren,L(N), die die Anzahl der erforderlichen Ebenen für N Einträge angibt.Abbildung 4-6 enthält eine Visualisierung, die bei der Bestimmung von L(N) hilft. Sie enthält 16 Einträge, die jeweils mit einem tiefgestellten Index gekennzeichnet sind, der bei _e1 oben beginnt und von links nach rechts ansteigt, bis es auf dieser Ebene keine weiteren Einträge mehr gibt, bevor er wieder beim ganz linken Eintrag der nächsten Ebene beginnt.

Abbildung 4-6. Ermitteln der benötigten Ebenen für einen binären Heap mit N Einträgen

Wenn es nur 7 Einträge in einem Haufen gäbe, würde es 3 Ebenen geben, die die Einträge _e1 bis _e7 enthalten. Für 8 Einträge wären vier Ebenen erforderlich. Wenn du den linken Pfeilen von oben folgst, kannst du sehen, dass die tiefgestellten Einträge einem bestimmten Muster folgen: _e1, _e2, _e4, _e8 und _e16, was darauf hindeutet, dass Potenzen von 2 eine Rolle spielen werden. Es stellt sich heraus, dass L(N) = 1 + floor(log(N)).

Tipp

Jede neue volle Ebene im binären Heap enthält mehr Einträge als die Gesamtzahl der Einträge in allen vorherigen Ebenen. Wenn du die Höhe eines binären Heaps um nur eine Ebene erhöhst, kann der binäre Heap mehr als doppelt so viele Einträge enthalten (insgesamt 2N + 1 Einträge, wobei N die Anzahl der vorhandenen Einträge ist)!

Du solltest dich bei Logarithmen daran erinnern, dass sich der Wert vonlog(N) um 1 erhöht, wenn du N verdoppelst. Dies wird mathematisch wie folgt dargestellt:log(2N) = 1 + log(N). Welche der vier Optionen inAbbildung 4-7 sind gültige max binäre Haufen?

Abbildung 4-7. Welche davon sind gültige max binäre Heaps?

Überprüfe zunächst die Eigenschaft "heap-shape" für jede dieser Optionen. Die Optionen #1 und #2 sind akzeptabel, da jede Ebene vollständig gefüllt ist. Option Nr. 3 ist akzeptabel, weil nur die letzte Ebene unvollständig ist und drei (von vier möglichen) Einträgen von links nach rechts enthält. Option 4 verstößt gegen die Heap-Eigenschaft, weil die letzte Ebene drei Einträge enthält, aber der letzte mögliche Eintrag fehlt.

Betrachte nun die Eigenschaft heap-ordered für max binary heaps, die sicherstellt, dass die Priorität jedes Elternteils größer oder gleich der Priorität seiner Kinder ist. Option 1 ist gültig, wie du bestätigen kannst, indem du jeden möglichen Pfeil überprüfst. Option #3 ist ungültig, weil der Eintrag mit der Priorität 8 ein rechtes Kind hat, dessen Priorität 9 höher ist. Option #2 ist ungültig, weil der Eintrag mit der Priorität 4 auf Ebene 0 eine geringere Priorität hat als seine beiden Kindeinträge.

Hinweis

Option 2 ist ein gültiges Beispiel für einen Min-Binär-Heap, bei dem die Priorität jedes übergeordneten Eintrags kleiner oder gleich der Priorität seiner Kinder ist. Min-Binärheaps werden in Kapitel 7 verwendet.

Ich muss sicherstellen, dass beide Heap-Eigenschaften nach enqueue() oderdequeue() (wodurch der Wert mit der höchsten Priorität im Max Heap entfernt wird) erhalten bleiben. Das ist wichtig, denn dann kann ich zeigen, dass beide Operationen in O(log N) durchgeführt werden können. Das ist eine deutliche Verbesserung gegenüber den in Tabelle 4-1 dokumentierten Ansätzen, die begrenzt waren, da entweder enqueue() oder dequeue() ein Worst-Case-Verhalten von O(N) hatten.

Einfügen einer (Wert, Priorität)

Nachdem enqueue(value, priority) auf einem max binary heap aufgerufen wurde, wo soll der neue Eintrag platziert werden? Hier ist eine Strategie, die immer funktioniert:

• Platziere den neuen Eintrag auf dem ersten freien Platz auf der letzten Ebene.

• Wenn diese Ebene voll ist, erweiterst du den Heap um eine neue Ebene und platzierst den neuen Eintrag an der äußersten linken Stelle der neuen Ebene.

In Abbildung 4-8 wird ein neuer Eintrag mit der Priorität 12 an der dritten Stelle der Ebene 4 eingefügt. Du kannst bestätigen, dass die Eigenschaft heap-shape gültig ist (denn die Einträge auf der Teilebene 4 beginnen von links ohne Lücken). Es könnte jedoch sein, dass die Eigenschaft heap-ordered jetzt verletzt wurde.

Die gute Nachricht ist, dass ich nur die Einträge neu anordnen muss, die im Pfad von dem neu platzierten Eintrag bis zum obersten Eintrag auf Ebene 0 liegen. Abbildung 4-10 zeigt das Endergebnis nach der Wiederherstellung der Heap-Ordered-Eigenschaft. Wie du siehst, wurden die Einträge im schattierten Pfad in abnehmender (oder gleicher) Reihenfolge von oben nach unten neu geordnet.

Abbildung 4-8. Der erste Schritt beim Einfügen eines Eintrags besteht darin, ihn an der nächsten verfügbaren Position zu platzieren

Hinweis

Ein Pfad zu einem bestimmten Eintrag in einem binären Heap ist eine Abfolge von Einträgen, die gebildet wird, indem du den Pfeilen (links oder rechts) von dem einzelnen Eintrag auf Ebene 0 folgst, bis du den bestimmten Eintrag erreichst.

Um den Max Heap so umzugestalten, dass er der Heap-Ordered-Eigenschaft entspricht, "schwimmt" der neu hinzugefügte Eintrag entlang dieses Pfades zu seiner richtigen Position, indem er paarweise vertauscht wird. Anhand dieses Beispiels zeigt Abbildung 4-8, dass der neu hinzugefügte Eintrag mit der Priorität 12 die Heap-Ordered-Eigenschaft außer Kraft setzt, da seine Priorität größer ist als die seines Elternteils mit der Priorität 2. Tausche diese beiden Einträge, um den Max Heap in Abbildung 4-9 zu erzeugen und fahre mit der Aufwärtsbewegung fort.

Abbildung 4-9. Im zweiten Schritt wird der Eintrag je nach Bedarf eine Ebene höher geschwommen

Du kannst bestätigen, dass die Struktur von 12 abwärts ein gültiger max binärer Heap mit zwei Einträgen ist. Der Eintrag mit der Nummer 12 macht die Heap-Ordered-Eigenschaft jedoch immer noch ungültig, da sein übergeordneter Eintrag eine Priorität von 9 hat, die kleiner ist, also tausche mit seinem übergeordneten Eintrag, wie in Abbildung 4-10 gezeigt.

Ab dem hervorgehobenen Eintrag 12 in Abbildung 4-10 ist die Struktur ein gültiger max binary heap. Als du die Einträge 9 und 12 vertauscht hast, musstest du dir keine Gedanken über die Struktur ab 8 und darunter machen , da alle diese Werte bekanntermaßen kleiner oder gleich 8 sind, was bedeutet, dass sie alle kleiner oder gleich 12 sein werden. Da 12 kleiner ist als sein übergeordneter Eintrag mit der Priorität 13, ist die Eigenschaft der Heap-Ordnung erfüllt.

Abbildung 4-10. Im dritten Schritt wird der Eintrag je nach Bedarf eine Ebene höher geschwommen

Versuche selbst, enqueue(value, 16) in den inAbbildung 4-10 dargestellten Heap einzutragen. Dabei wird der neue Eintrag zunächst an der vierten Stelle auf Ebene 4 platziert, als rechtes Kind des Eintrags mit der Priorität 9. Dieser neue Eintrag schwimmt dann bis zur Ebene 0, was zu dem in Abbildung 4-11 dargestellten maximalen Binärhaufen führt.

Abbildung 4-11. Hinzufügen eines Eintrags mit Priorität 16 schwimmt an die Spitze

Der schlimmste Fall ist, wenn du einen neuen Eintrag in die Warteschlange einträgst, dessen Priorität höher ist als jeder Eintrag im max binary heap. Die Anzahl der Einträge im Pfad ist 1 + floor(log(N)), was bedeutet, dass die maximale Anzahl der Swaps um eins kleiner ist, oder floor(log(N)). Jetzt kann ich klar sagen, dass die Zeit, um den maximalen binären Heap nach einer enqueue() Operation neu zu erstellen, O(logN) ist. Dieses großartige Ergebnis löst nur die Hälfte des Problems, denn ich muss auch sicherstellen, dass ich den Eintrag mit der höchsten Priorität im max binary heap effizient entfernen kann.

Den Wert mit der höchsten Priorität entfernen

Es ist ganz einfach, den Eintrag mit der höchsten Priorität in einem max. binären Heap zu finden - es ist immer der einzelne Eintrag auf Ebene 0 ganz oben. Aber du kannst diesen Eintrag nicht einfach entfernen, denn dann würde die Heap-Eigenschaft durch eine Lücke auf Ebene 0 verletzt werden. Glücklicherweise gibt es eine dequeue()Strategie, mit der du den obersten Eintrag entfernen und den Max Binary Heap effizient neu aufbauen kannst, wie ich in der nächsten Reihe von Abbildungen zeige:

1. Entferne den ganz rechten Eintrag auf der untersten Ebene und erinnere ihn. Die daraus resultierende Struktur erfüllt sowohl die Eigenschaften "geordneter Haufen" als auch "Haufenform".

2. Speichere den Wert für den Eintrag mit der höchsten Priorität auf Ebene 0, damit er zurückgegeben werden kann.

3. Ersetze den Eintrag auf Ebene 0 durch den Eintrag, den du von der untersten Ebene des Heaps entfernt hast. Das könnte die Heap-Ordered-Eigenschaft zerstören.

Um dieses Ziel zu erreichen, entferne und erinnere zunächst den Eintrag 9, wie inAbbildung 4-12 gezeigt; die resultierende Struktur bleibt ein Heap. Als Nächstes notierst du den Wert, der mit der höchsten Priorität auf Ebene 0 verbunden ist, damit er zurückgegeben werden kann (hier nicht gezeigt).

Abbildung 4-12. Der erste Schritt besteht darin, den untersten Eintrag zu entfernen

Ersetze abschließend den einzelnen Eintrag auf Ebene 0 durch den entfernten Eintrag, wodurch der in Abbildung 4-13 gezeigte kaputte Max Heap entsteht. Wie du siehst, ist die Priorität des einzelnen Eintrags auf Ebene 0 nicht höher als die seines linken (mit Priorität 15) und rechten (mit Priorität 14) Kinds. Um den Max Heap wiederherzustellen, musst du diesen Eintrag an eine Stelle weiter unten im Heap "versenken", um die Heap-Ordnung wiederherzustellen.

Abbildung 4-13. Kaputter Heap durch Swapping des letzten Eintrags mit Level 0

Ausgehend von dem ungültigen Eintrag (d.h. dem Eintrag der Ebene 0 mit der Priorität 9) wird ermittelt, welcher seiner Untereinträge (d.h. der linke oder der rechte) die höhere Priorität hat - wenn nur der linke Untereintrag existiert, wird dieser verwendet. In diesem Beispiel hat das linke Kind mit der Priorität 15 eine höhere Priorität als das rechte Kind mit der Priorität 14. Abbildung 4-14 zeigt das Ergebnis des Austauschs des obersten Eintrags mit dem höher gewählten Kindeintrag.

Abbildung 4-14. Vertauschen des obersten Eintrags mit seinem linken Kind, das eine höhere Priorität hatte

Wie du siehst, ist die gesamte Unterstruktur, die auf dem Eintrag mit der Priorität 14 auf Ebene 1 basiert, ein gültiger Max Binary Heap und muss daher nicht geändert werden. Der neu ausgetauschte Eintrag (mit der Priorität 9) verstößt jedoch gegen die Heap-Ordered-Eigenschaft (er ist kleiner als die Priorität seiner beiden Kinder). Daher muss dieser Eintrag weiter nach links "sinken", wie in Abbildung 4-15 dargestellt, da der Eintrag mit der Priorität 13 der größere seiner beiden Kindereinträge ist.

Abbildung 4-15. Eine weitere Ebene nach unten sinken

Fast geschafft! Abbildung 4-15 zeigt, dass der Eintrag mit der Priorität 9 ein rechtes Kind hat, dessen Priorität 12 höher ist. Also tauschen wir diese Einträge aus, wodurch die Heap-Ordered-Eigenschaft für diesen Heap endlich wiederhergestellt wird, wie in Abbildung 4-16 zu sehen ist.

Abbildung 4-16. Der resultierende Heap nach dem Absenken des Eintrags an seinen richtigen Platz

Es gibt keinen einfachen Weg der angepassten Einträge, wie wir es beim Einreihen eines neuen Eintrags in die Prioritätswarteschlange gesehen haben, aber es ist dennoch möglich, die maximale Anzahl der Wiederholungen des "Sinkdown"-Schritts zu bestimmen, nämlich einen Wert, der kleiner ist als die Anzahl der Ebenen im max binary heap, oderfloor(log(N)).

Du kannst auch zählen, wie oft die Prioritäten von zwei Einträgen miteinander verglichen wurden. Bei jedem "Sinkdown"-Schritt gibt es höchstens zwei Vergleiche - einen Vergleich, um den größeren der beiden Geschwistereinträge zu finden, und dann einen Vergleich, um festzustellen, ob der übergeordnete Eintrag größer ist als der größere dieser beiden Geschwister. Insgesamt bedeutet das, dass die Anzahl der Vergleiche nicht größer als 2 × floor(log(N)) ist.

Es ist unglaublich wichtig, dass der max binary heap sowohl einen Eintrag hinzufügen als auch den Eintrag mit der höchsten Priorität in einer Zeit entfernen kann, die im schlimmsten Fall direkt proportional zu log(N) ist. Jetzt ist es an der Zeit, diese Theorie in die Praxis umzusetzen, indem wir zeigen, wie man einen binären Heap mit einem gewöhnlichen Array implementiert.

Hast du bemerkt, dass die Eigenschaft "heap-shape" dafür sorgt, dass du alle Einträge der Reihe nach von links nach rechts lesen kannst, von Ebene 0 abwärts durch jede nachfolgende Ebene? Ich kann mir diese Erkenntnis zunutze machen, indem ich einen binären Heap in einem gewöhnlichen Array speichere.

Einen binären Heap in einem Array repräsentieren

Abbildung 4-17 zeigt, wie man einen max. binären Heap mit N = 18 Einträgen in einem festen Array der Größe M > N speichert. Dieser max. binäre Heap mit fünf Ebenen kann in einem gewöhnlichen Array gespeichert werden, indem jede Position im binären Heap einer eindeutigen Indexposition zugeordnet wird. Jedes gestrichelte Kästchen enthält eine ganze Zahl, die der Indexposition in dem Array entspricht, in dem der Eintrag aus dem binären Heap gespeichert ist. Noch einmal: Bei der Darstellung eines binären Heaps zeige ich nur die Prioritäten der Einträge.

Abbildung 4-17. Speichern eines maximalen binären Heaps in einem Array

Jeder Eintrag hat einen entsprechenden Platz im Array storage[]. Um alle Berechnungen zu vereinfachen, ist der Ort storage[0] unbenutzt und speichert nie einen Eintrag. Der oberste Eintrag mit der Priorität 15 befindet sich instorage[1]. Wie du siehst, befindet sich sein linkes Kind mit der Priorität 13 in storage[2]. Wenn der Eintrag in storage[k] ein linkes Kind hat, ist das storage[2*k]; Abbildung 4-17 bestätigt diese Beobachtung (schau dir einfach die gestrichelten Kästchen an). Wenn der Eintrag in storage[k]ein rechtes Kind hat, befindet sich dieser Eintrag in storage[2*k+1].

Für k > 1 kann das Elternteil des Eintrags in storage[k] instorage[k//2] gefunden werden, wobei k//2 der ganzzahlige Wert ist, der sich aus dem Ergebnis von k geteilt durch 2 ergibt. Indem du den obersten Eintrag des Heaps in storage[1] platzierst, führst du einfach eine ganzzahlige Division durch zwei durch, um den Elternort eines Eintrags zu berechnen. Der Elternteil des Eintrags in storage[5] (mit einer Priorität von 11) befindet sich in storage[2], weil 5//2 = 2 ist.

Der Eintrag in storage[k] ist ein gültiger Eintrag, wenn 0 < k ≤ N, wobei N die Anzahl der Einträge im max binary heap darstellt. Das bedeutet, dass der Eintrag unter storage[k] keine Kinder hat, wenn 2 × k > N ist; zum Beispiel hat der Eintrag unter storage[10] (der die Priorität 1 hat) kein linkes Kind, weil 2 × 10 = 20 > 18. Du weißt auch, dass der Eintrag unter storage[9](der zufällig die Priorität 9 hat) kein rechtes Kind hat, weil 2 × 9 + 1 = 19 > 18 ist.

Umsetzung von Swim and Sink

Um einen maximalen binären Heap zu speichern, beginnst du mit einer Entry, die eine value mit der dazugehörigen priority hat:

class Entry:
  def __init__(self, v, p):
    self.value = v
    self.priority = p

Listing 4-2 speichert einen maximalen binären Heap in einem Array,storage. Wenn er instanziiert wird, ist die Länge von storage um eins größer als der Parameter size, um den zuvor beschriebenen Berechnungen zu entsprechen, bei denen der erste Eintrag in storage[1] gespeichert wird.

Es gibt zwei Hilfsmethoden, die die Darstellung des Codes vereinfachen. Du hast gesehen, wie oft ich überprüft habe, ob ein Eintrag eine kleinere Priorität als ein anderer Eintrag hat. Die Funktion less(i,j) gibtTrue zurück, wenn die Priorität des Eintrags in storage[i] kleiner ist als die Priorität des Eintrags in storage[j]. Wenn ich nach oben schwimme oder nach unten sinke, muss ich zwei Einträge vertauschen. Die Funktion swap(i,j) vertauscht die Positionen der Einträge in storage[i] und storage[j].

Listing 4-2. Heap-Implementierung mit den Methoden enqueue() und swim()

class PQ:
  def less(self, i, j):                               
    return self.storage[i].priority < self.storage[j].priority

  def swap(self, i, j):                               
    self.storage[i],self.storage[j] = self.storage[j],self.storage[i]

  def __init__(self, size):                           
    self.size = size
    self.storage = [None] * (size+1)
    self.N = 0

  def enqueue(self, v, p):                            
    if self.N == self.size:
      raise RuntimeError ('Priority Queue is Full!')

    self.N += 1
    self.storage[self.N] = Entry(v, p)
    self.swim(self.N)

  def swim(self, child):                              
    while child > 1 and self.less(child//2, child):   
      self.swap(child, child//2)                      
      child = child // 2                              

less() bestimmt, ob storage[i] eine niedrigere Priorität als storage[j] hat.

swap() schaltet die Positionen der Einträge i und j um.

storage[1] bis storage[size] werden die Einträge gespeichert;storage[0] ist unbenutzt.

Um einen enqueue Eintrag (v, p) zu erstellen, platziere ihn an der nächsten freien Stelle und schwimme ihn nach oben.

swim() macht das Array storage so um, dass es der Heap-Ordered-Eigenschaft entspricht.

Das Elternteil des Eintrags in storage[child] befindet sich in storage[child//2], wobei child//2 das ganzzahlige Ergebnis der Division von child durch 2 ist.

Tausche die Einträge auf storage[child] und der übergeordneten Seite storage[child//2].

Fahre nach oben fort, indem du child nach Bedarf auf den übergeordneten Standort setzt.

Die Methode swim() ist wirklich kurz! Der Eintrag, der durch child identifiziert wird, ist der neue Eintrag in der Warteschlange, während child//2 der übergeordnete Eintrag ist, falls er existiert. Wenn der übergeordnete Eintrag eine niedrigere Priorität als der untergeordnete Eintrag hat, werden die beiden Einträge getauscht und der Prozess wird aufwärts fortgesetzt.

Abbildung 4-18 zeigt die Änderungen an storage, die durchenqueue(value, 12) in Abbildung 4-8 ausgelöst wurden. Jede nachfolgende Zeile entspricht einer früher identifizierten Abbildung und zeigt die Einträge, die sich in storage ändern. Die letzte Zeile stellt einen maximalen binären Heap dar, der den Eigenschaften "heap-ordered" und "heap-shape" entspricht.

Abbildung 4-18. Änderungen an der Speicherung nach dem Enqueue in Abbildung 4-8

Der Weg vom obersten Eintrag zum neu eingefügten Eintrag mit Priorität 12 besteht aus fünf Einträgen, wie in Abbildung 4-18 schattiert dargestellt. Nach zweimaligem Durchlaufen der while -Schleife in swim() wird der Eintrag mit der Priorität 12 mit seinem Elternteil vertauscht und schwimmt schließlich bis zu storage[4], wo er die Eigenschaft der Heap-Order erfüllt. Die Anzahl der Tauschvorgänge wird nie größer sein als log(N), wobei N die Anzahl der Einträge im binären Heap ist.

Die Implementierung in Listing 4-3 enthält die Methode sink(), um die Struktur des max binary heap wiederherzustellen, nachdem dequeue() aufgerufen wurde.

Listing 4-3. Heap-Implementierung abgeschlossen mit den Methoden dequeue() und sink()

  def dequeue(self):
    if self.N == 0:
      raise RuntimeError ('PriorityQueue is empty!')

    max_entry = self.storage[1]                         
    self.storage[1] = self.storage[self.N]              
    self.storage[self.N] = None
    self.N -= 1                                         
    self.sink(1)
    return max_entry.value                              

  def sink(self, parent):
    while 2*parent <= self.N:                           
      child = 2*parent
      if child < self.N and self.less(child, child+1):  
        child += 1
      if not self.less(parent, child)                   
        break
      self.swap(child, parent)                          
      parent = child

Speichere den Eintrag der höchsten Priorität auf der Ebene 0.

Ersetze den Eintrag in storage[1] durch einen Eintrag aus der untersten Ebene des Haufens und lösche ihn aus storage.

Reduziere die Anzahl der Einträge , bevor du sink auf storage[1] aufrufst.

Gibt den Wert für den Eintrag mit der höchsten Priorität zurück.

Prüfe weiter, solange ein Elternteil ein Kind hat.

Wähle das rechte Kind aus, wenn es existiert und größer als das linke Kind ist.

Wenn parent nicht kleiner als child ist, ist die Eigenschaft "heap-ordered" erfüllt.

Tausche, wenn nötig, und sinke weiter nach unten, indem du child als neue parent benutzt.

Abbildung 4-19 zeigt die Änderungen an storage, die vondequeue() auf der Grundlage des inAbbildung 4-11 gezeigten anfänglichen max binary heap vorgenommen wurden. Die erste Zeile in Abbildung 4-19 zeigt das Array mit 19 Einträgen. In der zweiten Zeilewird der letzte Eintrag im Heap mit der Priorität 9 zum obersten Eintrag im max binary Heap, wodurch die Heap-Ordered-Eigenschaft gebrochen wird; außerdem enthält der Heap jetzt nur noch 18 Einträge, da einer gelöscht wurde.

Abbildung 4-19. Änderungen in der Speicherung nach der Dequeue in Abbildung 4-11

Nach drei aufeinanderfolgenden Durchläufen durch die while Schleife in sink() ist der Eintrag mit der Priorität 9 an eine Stelle zurückgefallen, die die Heap-Ordered-Eigenschaft gewährleistet. In jeder Zeile ist der am weitesten links stehende Eintrag der Eintrag mit der Priorität 9 und die schattierten Einträge rechts davon sind seine Kindereinträge. Immer wenn der übergeordnete Eintrag mit der Priorität 9 kleiner ist als einer seiner Kinder, muss er nach unten sinken, um mit dem größeren seiner Kinder getauscht zu werden. Die Anzahl der Tauschvorgänge wird nie mehr als log(N) betragen.

Die Methode sink() ist am schwierigsten zu visualisieren, weil es keinen geraden Pfad gibt, dem man folgen kann, wie bei swim(). In der endgültigen Darstellung vonstorage in Abbildung 4-19 kannst du sehen, dass der hervorgehobene Eintrag mit der Priorität 9 nur ein schattiertes Kind hat (mit der Priorität 2). Wennsink() endet, weißt du, dass der Eintrag, der gesunken ist, entweder eine Indexstelle p erreicht hat, an der er keine Kinder hat (weil 2 × p eine ungültige storage Indexstelle ist, die größer als N ist), oder er ist größer oder gleich (d.h. nicht kleiner als) dem größeren seiner Kindereinträge.

Warnung

Die Reihenfolge der Anweisungen in dequeue() ist entscheidend. Insbesondere musst du N um 1 verringern, bevor du sink(1) aufrufst, sonst denkt sink()fälschlicherweise, dass die Indexposition in storage, die dem kürzlich aus der Warteschlange entfernten Eintrag entspricht , noch Teil des Heaps ist. Im Code siehst du, dass storage[N] auf None gesetzt wird, um sicherzustellen, dass der Eintrag nicht fälschlicherweise für einen Teil des Heaps gehalten wird.

Wenn du dich selbst davon überzeugen willst, dass die Logik von dequeue() korrekt ist, dann betrachte, wie sie mit einem Heap arbeitet, der nur einen einzigen Eintrag enthält. Es ruft max_entry auf und setzt N auf 0, bevor es sink() aufruft, was nichts bewirkt, da 2 × 1 > 0.

Zusammenfassung

Die binäre Heap-Struktur bietet eine effiziente Implementierung des abstrakten Datentyps der Prioritätswarteschlange. Zahlreiche Algorithmen, wie die in Kapitel 7 besprochenen, hängen von Prioritätswarteschlangen ab.

• Du kannst enqueue() einen (Wert, Priorität) Eintrag in O(log N) Leistung.

• Du kannst dequeue() den Eintrag mit der höchsten Priorität in O(log N) Leistung.

• Du kannst die Anzahl der Einträge in einem Heap in O(1) Leistung melden.

In diesem Kapitel habe ich mich ausschließlich auf max binäre Heaps konzentriert. Du brauchst nur eine kleine Änderung vorzunehmen, um einen min binary heap zu realisieren, bei dem Einträge mit höherer Priorität kleinere numerische Prioritätswerte haben. Dies wird inKapitel 7 relevant werden. In Listing 4-2 musst du nur die Methode less()umschreiben, um größer-als (>) statt kleiner-als (<) zu verwenden. Alle anderen Codes bleiben unverändert.

def less(self, i, j):
  return self.storage[i].priority > self.storage[j].priority

Während eine Prioritätswarteschlange im Laufe der Zeit wachsen oder schrumpfen kann, legt die Heap-basierte Implementierung eine anfängliche Größe, M, für die Speicherung der N < M Einträge fest. Sobald der Heap voll ist, können keine weiteren Einträge mehr in die Prioritätswarteschlange aufgenommen werden. Es ist möglich, die Speicherung automatisch zu vergrößern (und zu verkleinern), ähnlich wie in Kapitel 3 gezeigt. Solange du die geometrische Größenanpassung verwendest, die die Größe der Speicherung verdoppelt, wenn sie voll ist, bleibt die amortisierte Gesamtleistung für enqueue() O(log N).

Herausforderung Übungen

1. Es ist möglich, ein festes Array, storage, als Datenstruktur zu verwenden, um eine Warteschlange effizient zu implementieren, so dass die Operationen enqueue() und dequeue()die Leistung O(1) haben. Dieser Ansatz wird als zirkuläre Warteschlange bezeichnet, die den neuartigen Vorschlag macht, dass der erste Wert im Array nicht immer storage[0] ist. Stattdessen werden first, die Indexposition für den ältesten Wert in der Warteschlange, und last, die Indexposition für den nächsten Wert in der Warteschlange, wie inAbbildung 4-20 dargestellt, gespeichert.

   

   Abbildung 4-20. Verwendung eines Arrays als zirkuläre Warteschlange

   Wenn du Werte in die Warteschlange aufnimmst und wieder entfernst, musst du diese Werte sorgfältig manipulieren. Es ist nützlich, N, die Anzahl der Werte in der Warteschlange, im Auge zu behalten. Kannst du die Implementierung inListing 4-4 vervollständigen und bestätigen, dass diese Operationen in konstanter Zeit abgeschlossen werden? Du solltest davon ausgehen, dass du den Operator modulo % in deinem Code verwenden wirst.

   Listing 4-4. Vervollständige diese Queue Implementierung einer zirkulären Warteschlange

   class Queue:
     def __init__(self, size):
       self.size = size
       self.storage = [None] * size
       self.first = 0
       self.last = 0
       self.N = 0
   
     def is_empty(self):
       return self.N == 0
   
     def is_full(self):
       return self.N == self.size
   
     def enqueue(self, item):
       """If not full, enqueue item in O(1) performance."""
   
     def dequeue(self):
       """If not empty, dequeue head in O(1) performance."""

2. Füge N = 2^k - 1 Elemente in aufsteigender Reihenfolge in einen leeren max. binären Heap der Größe N ein. Wenn du die zugrunde liegende Anordnung untersuchst, die sich daraus ergibt (abgesehen von der Indexposition 0, die unbenutzt ist), kannst du die Indexpositionen für die größten k Werte in der Speicherung vorhersagen? Wenn du N Elemente in absteigender Reihenfolge in einen leeren Max Heap einfügst, kannst du die Indexpositionen für alle N Werte vorhersagen?

3. Erfinde einen Algorithmus, der ein Array der Größe M + N mit den kombinierten Elementen von M und N in aufsteigender Reihenfolge mit O(M log M + N log N) Leistung zurückgibt. Erstelle eine Tabelle mit der Laufzeitleistung, um empirisch zu beweisen, dass dein Algorithmus funktioniert.

4. Verwende einen max binary heap, um die k kleinsten Werte aus einer Sammlung von N Elementen in O(N log k) zu finden. Erstelle eine Tabelle mit der Laufzeitleistung, um empirisch zu beweisen, dass dein Algorithmus funktioniert.

5. In hat jeder Elterneintrag bis zu zwei Kinder. Betrachten wir eine alternative Strategie, die ich einen faktoriellen Heap nenne, bei dem der oberste Eintrag zwei Kinder hat; jedes dieser Kinder hat drei Kinder (die ich Enkelkinder nenne). Jedes dieser Enkelkinder hat vier Kinder und so weiter, wie in Abbildung 4-21 dargestellt. Auf jeder weiteren Ebene haben die Einträge ein weiteres Kind. Die Eigenschaften "heap-shape" und "heap-ordered" bleiben erhalten. Vervollständige die Implementierung, indem du den faktoriellen Heap in einem Array speicherst, und führe eine empirische Auswertung durch, um zu bestätigen, dass die Ergebnisse langsamer sind als der maximale binäre Heap. Die Klassifizierung der Laufzeitleistung ist komplizierter, aber du solltest in der Lage sein festzustellen, dass sie O(log N/log(log N)) ist.

   

   Abbildung 4-21. Eine neuartige faktorielle Heap-Struktur

6. Erweitere die Implementierung von PQin diesem Kapitel mit Hilfe der geometrischen Größenanpassungsstrategie aus Kapitel 3, um die Größe der Speicherung automatisch zu verdoppeln, wenn sie voll ist, und zu halbieren, wenn sie ¼ voll ist.

7. Ein Iterator für eine Array-basierte Datenstruktur im Heap sollte die Werte in der Reihenfolge ausgeben , in der sie aus der Warteschlange genommen werden, ohne das zugrunde liegende Array zu verändern (da ein Iterator keine Nebeneffekte haben sollte). Das ist jedoch nicht so einfach zu bewerkstelligen, da das Auflösen von Werten die Struktur des Heaps verändern würde. Eine Lösung besteht darin, eine Generatorfunktioniterator(pq) zu erstellen, die eine Prioritätswarteschlange pq aufnimmt und eine separate Prioritätswarteschlange pqit erstellt, deren Werte Indexpositionen im Array storage für pq sind und deren Prioritäten den entsprechenden Prioritäten für diese Werte entsprechen. pqit greift direkt auf das Array storage für pq zu, um die zurückzugebenden Einträge zu verfolgen, ohne den Inhalt von storage zu stören.

   Vervollständige die folgende Implementierung, die damit beginnt, dass du inpqit die Indexposition 1 einfügst, die auf das Paar in pq mit der höchsten Priorität verweist. Schließe den Rest der Schleife while ab:

   def iterator(pq):
     pqit = PQ(len(pq))
     pqit.enqueue(1, pq.storage[1].priority)
   
     while pqit:
       idx = pqit.dequeue()
       yield (pq.storage[idx].value, pq.storage[idx].priority)
   
       ...

   Solange die ursprüngliche pq unverändert bleibt, wird dieser Iterator jeden der Werte in der Reihenfolge der Priorität liefern.