Heap Kind-links Index

Worum geht es?

In einem Array-basierten Binär-Heap (0-basiert) liegt das linke Kind des Knotens i an Position 2i + 1. Diese Formel — gemeinsam mit Rechts = 2i + 2 und Eltern = ⌊(i−1)/2⌋ — bildet die komplette Navigationsarithmetik des Heaps.

Sie wird in jedem Sift-Down verwendet: nach einem extractMin wird das letzte Element an die Wurzel kopiert und nach unten propagiert. Bei jedem Schritt vergleicht der Algorithmus das aktuelle Element mit dem kleineren der beiden Kinder und tauscht falls nötig.

Die Formel

Links = 2 · i + 1

Umstellung:
    i = (Links − 1) / 2

Die Variablen

Minimal-Beispiel

Linkes Kind von Index 4:

Links = 2 · 4 + 1
      = 9

Praxis-Beispiele

Beispiel 1 — Existenz prüfen

In einem Heap der Größe n existiert das linke Kind genau dann, wenn 2i + 1 < n. Für i = 7 in einem Heap mit n = 15:

Links = 2 · 7 + 1 = 15
15 < 15 ?  → nein
⇒ Knoten 7 ist ein Blatt.

Beispiel 2 — Sift-Down-Pfad

Sift-Down von der Wurzel in einem Heap mit n = 20 (immer linkes Kind, falls kleiner):

i =  0 → Links =  1
i =  1 → Links =  3
i =  3 → Links =  7
i =  7 → Links = 15
i = 15 → Links = 31 ≥ 20  ⇒ Stopp.

Beispiel 3 — Build-Heap

Beim Aufbau von Heap aus unsortiertem Array (Floyd-Algorithmus) wird Sift-Down von i = ⌊n/2⌋ − 1 abwärts ausgeführt. Für n = 16 also bei i = 7, 6, 5, …, 0.