Aufbau eines Max-Heaps und eines Min-Heaps

Beide Heaps starten mit denselben Zahlen. Wir bearbeiten die inneren Knoten von rechts nach links. Für jeden Startknoten wird zuerst der Max-Heap und danach der Min-Heap aktualisiert.

Max-Heap

Jeder Elternknoten ist mindestens so groß wie seine Kinder.

Array

Binärbaum

Min-Heap

Jeder Elternknoten ist höchstens so groß wie seine Kinder.

Array

Binärbaum

ms
aktueller Elternknoten verglichenes Kind Vertauschung fertiger Teilbaum
Array und Baum sind zwei Darstellungen derselben Daten. Zum Index i gehören die Kinder 2*i + 1 und 2*i + 2. Der letzte innere Knoten liegt bei floor(n/2) − 1. Beide Heaps werden hier in O(n) aufgebaut. Es findet noch keine Sortierung statt.

Ablauf / Protokoll