Binärer Heap: Eine Prioritätswarteschlange im Array

Fünfzehn Schlüssel liegen in einem Array, das zugleich einen Baum darstellt: Die beiden Kindknoten der Position i stehen an den Positionen 2i + 1 und 2i + 2. Baue daraus einen Heap, entweder durch einzelnes Einfügen oder ab dem letzten Elternknoten. Verfolge jeden Vergleich und jeden Tausch. Entnimm dann den kleinsten Schlüssel und beobachte, wie der nächstkleinere an die Wurzel rückt.

Rechenbeispiel — Binärer Heap: Eine Prioritätswarteschlange im Array

Schlüssel	15
Durch einzelnes Einfügen aufgebaut	34 Vergleiche, 34 Tauschvorgänge
Maximale Vergleichszahl beim einzelnen Einfügen	34
Ab dem letzten Elternknoten aufgebaut	22 Vergleiche, 11 Tauschvorgänge

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Binärer Heap: Eine Prioritätswarteschlange im Array

Ein binärer Min-Heap ist ein Array, in dem der Schlüssel an jeder Position i höchstens so groß ist wie die Schlüssel an den Positionen 2i + 1 und 2i + 2, seinen Kindknoten. Der Elternknoten der Position i steht an Position ⌊(i − 1) / 2⌋. So gelesen bildet das Array einen vollständigen Binärbaum. Der kleinste Schlüssel steht immer an Position 0, der Wurzel. Zum Einfügen legst du den Schlüssel ans Ende und lässt ihn aufsteigen: Tausche ihn mit seinem Elternknoten, solange er kleiner ist als dieser. Um den kleinsten Schlüssel zu entnehmen, setzt du den letzten an die Wurzel und lässt ihn absinken: Tausche ihn mit seinem kleineren Kindknoten, solange dieser kleiner ist als er. Ein so verwendeter Heap ist eine Prioritätswarteschlange.

Was die einzelnen Symbole bedeuten

n: Anzahl der Schlüssel im Heap
i: Position im Array, ab 0 gezählt
h: Höhe einer Position: Anzahl der Ebenen unter ihr, ⌊log₂(n / (i + 1))⌋

Setzt voraus: Bei einem Vergleich werden zwei Schlüssel miteinander verglichen; bei einem Tausch wechseln sie ihre Positionen. Das Versetzen des letzten Schlüssels an die Wurzel bei einer Entnahme zählt als keines von beidem. Ist ein Schlüssel gleich seinem Elternknoten oder seinem kleineren Kindknoten, bleibt er stehen. Bei zwei gleichen Kindknoten wird der linke gewählt. Dieser Heap hält den kleinsten Schlüssel an der Wurzel. Bei einem Max-Heap sind alle Vergleichsrichtungen umgekehrt. Du kannst bis zu fünfzehn Schlüssel von 0 bis 99 verwenden, damit der gesamte Baum auch auf ein Smartphone passt. Die letzte Tabellenzeile zählt Anordnungen verschiedener Schlüssel.

Beim Einfügen zählt die Tiefe, beim Aufbau von unten die Höhe 🖖

Klick auf Absteigend, einzeln. Jeder neue Schlüssel ist kleiner als alle bereits im Heap vorhandenen. Er steigt von unten bis zur Wurzel auf, mit einem Vergleich und einem Tausch pro Ebene: 0 für die Wurzel, je 1 für die nächsten 2 Schlüssel, je 2 für die nächsten 4 und je 3 für die letzten 8. Das ergibt 34. Klick nun auf Absteigend, von unten. Dieselben fünfzehn Schlüssel liegen zunächst in ihrer Eingabereihenfolge im Array. Von Position 6 bis zurück zu 0 wird jeder Schlüssel mit Kindknoten nach unten verschoben. Ein Schlüssel kann nur so viele Ebenen absinken, wie unter ihm liegen. Acht der fünfzehn Positionen sind Blätter. Gerade die Positionen, für die das erste Verfahren jeweils drei Ebenen durchlaufen musste, kosten hier nichts. Die Höhen ergeben zusammen 11; bei 2 Vergleichen pro Ebene sind das 22. In jedem Heap ist die Summe der Höhen gleich n minus der Anzahl der Ziffern 1 in der Binärdarstellung von n. Deshalb braucht dieser Aufbau stets weniger als 2n Vergleiche. Bei 1.023 Schlüsseln in absteigender Reihenfolge benötigen die beiden Verfahren 8.194 und 2.026 Vergleiche.

Aufsteigend brauchen beide Verfahren dieselben 14 Vergleiche 🖖

Klick auf Aufsteigend, einzeln. Jeder neue Schlüssel ist bereits mindestens so groß wie sein Elternknoten: ein Vergleich, kein Tausch, insgesamt 14 Vergleiche. Wechsle zu Ab dem letzten Elternknoten. Wieder sind es 14, denn jeder Elternknoten vergleicht seine beiden Kindknoten miteinander und dann den kleineren mit sich selbst. Danach ist er fertig. 14 ist für beide Verfahren die Untergrenze: Jeder Schlüssel außer der Wurzel muss mindestens einmal verglichen werden. Oberhalb dieser Grenze unterscheiden sich die Verfahren. Beim einzelnen Einfügen führt eine absteigende Eingabereihenfolge bis zur maximalen Vergleichszahl. Zufällig gemischte Schlüssel liegen deutlich näher an der Untergrenze. Bei 200 zufälligen Mischungen von 1.000 Schlüsseln brauchte das einzelne Einfügen im Mittel 2.235 Vergleiche, der Aufbau von unten 1.862. Dieselben Schlüssel in absteigender Reihenfolge benötigen beim einzelnen Einfügen 7.987 Vergleiche. Bei fünfzehn Schlüsseln ist der Unterschied klein. Klick ein paarmal auf Mischen: Gelegentlich kommt das einzelne Einfügen mit weniger Vergleichen aus.

Ein Heap ist noch lange nicht sortiert 🖖

Ein Heap garantiert, dass kein Schlüssel größer ist als seine Kindknoten. Von den 5.040 Anordnungen von sieben verschiedenen Schlüsseln erfüllen 80 diese Bedingung. Der kleinste Schlüssel muss an der Wurzel stehen. Beliebige drei der übrigen sechs dürfen den linken Teilbaum bilden, und jeder Teilbaum muss selbst ein Heap sein. Die Anzahl ergibt sich aus 7!, geteilt durch die Größen aller Teilbäume; das Produkt dieser Größen ist 7 · 3 · 3. Für fünfzehn Schlüssel zeigt die Ergebnistabelle 21.964.800 Heaps unter 1.307.674.368.000 Anordnungen. Genau eine davon ist sortiert. Diese Freiheit bei der Anordnung hält den Aufwand beim Aufbau klein. Die sortierte Folge entsteht beim Entnehmen der einzelnen Schlüssel. Klick auf Heapsort. Nach jeder Entnahme der Wurzel füllt der letzte Schlüssel die Lücke und sinkt ab. So gelangt der nächstkleinere an die Wurzel. Die zwölf Schlüssel werden in der Reihenfolge 3, 7, 12 und weiter bis 93 entnommen.

Aufgabe vollständig gelöst

Wie viele Vergleiche brauchen die beiden Aufbauverfahren bei rund tausend Schlüsseln? 4 Schritte
Klick auf Absteigend, einzeln und danach auf Absteigend, von unten. Erkläre, wie die 34 und die 22 zustande kommen. Betrachte dann 1.023 Schlüssel in absteigender Eingabereihenfolge. Wie viele Vergleiche braucht jedes Verfahren?

Öffne diese Aufgabe im Tool
1. Position i liegt in Tiefe ⌊log₂(i + 1)⌋: 1 Position in Tiefe 0, 2 in Tiefe 1, 4 in Tiefe 2 und 8 in Tiefe 3. Bei absteigender Eingabereihenfolge ist jeder neue Schlüssel der bisher kleinste. Er steigt bis zur Wurzel auf, mit einem Vergleich und einem Tausch pro Ebene: 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34.
  
  $0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34$
2. Beim Aufbau ab dem letzten Elternknoten zählt die Höhe: 3 für die Wurzel, 2 für die Positionen 1 und 2, 1 für die 4 Positionen in Tiefe 2 und 0 für die 8 Blätter. Die Summe ist 11. Bei absteigender Eingabereihenfolge sinkt jeder Schlüssel so weit wie möglich. Mit fünfzehn Schlüsseln hat jeder Elternknoten zwei Kindknoten, sodass jede durchlaufene Ebene 2 Vergleiche kostet: 22 Vergleiche und 11 Tauschvorgänge.
  
  $3 + 2 \cdot 2 + 4 \cdot 1 = 11, 2 \times 11 = 22$
3. 1.023 = 2¹⁰ − 1 ergibt einen vollständig besetzten Baum mit 10 Ebenen und 2ᵈ Positionen in Tiefe d. Beim einzelnen Einfügen entspricht die Vergleichszahl der Summe der Tiefen: 1 · 2 + 2 · 4 + 3 · 8 + ⋯ + 9 · 512 = 8.194 Vergleiche und ebenso viele Tauschvorgänge.
  
  $d = 0 \sum 9 d \cdot 2^{d} = 8 \cdot 2^{10} + 2 = 8194$
4. Beim Aufbau ab dem letzten Elternknoten ist die Vergleichszahl doppelt so groß wie die Summe der Höhen. Es gibt 2⁹ Positionen der Höhe 0, 2⁸ der Höhe 1 und so weiter bis zur Wurzel mit Höhe 9: 1 · 256 + 2 · 128 + ⋯ + 9 · 1 = 1.013. Das ist 1.023 minus die 10 Ziffern 1 in seiner Binärdarstellung. Die doppelte Summe ergibt 2.026 Vergleiche, dazu kommen 1.013 Tauschvorgänge.
  
  $h = 0 \sum 9 h \cdot 2^{9 - h} = 1023 - 10 = 1013, 2 \times 1013 = 2026$
Antwort

8.194 Vergleiche beim einzelnen Einfügen, 2.026 beim Aufbau ab dem letzten Elternknoten, also etwa 8 gegenüber 2 pro Schlüssel. Die meisten Positionen eines Heaps haben eine große Tiefe und eine geringe Höhe. Beim Einfügen bestimmt die Tiefe den Aufwand, beim Aufbau ab dem letzten Elternknoten die Höhe. Das Werkzeug erlaubt höchstens fünfzehn Schlüssel. Dort liefert dieselbe Rechnung die angezeigten 34 und 22.

$8194 against 2026$

Lernpfad

Was eine Datenstruktur mit wenig Aufwand leistet

Quellen (2)

Heapsort as first published: J. W. J. Williams, "Algorithm 232: Heapsort," Communications of the ACM 7(6), 347–348, June 1964.
The heap-based sort published six months later, close to the version used today: Robert W. Floyd, "Algorithm 245: Treesort 3," Communications of the ACM 7(12), 701, December 1964.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.