Heap Kind-rechts Index

Worum geht es?

Das rechte Kind des Knotens i in einem 0-basierten Array-Heap liegt bei Index 2i + 2, also direkt neben dem linken Kind (Links = 2i + 1). Diese Aneinanderreihung ist gewollt: beide Kinder liegen im Speicher unmittelbar nebeneinander und können in einer einzigen Cache-Line stehen.

Bei jedem Sift-Down in einer Priority-Queue oder im Heap-Sort vergleicht der Algorithmus beide Kinder, wählt das kleinere (Min-Heap) bzw. größere (Max-Heap) aus und tauscht mit der Eltern-Position — bis die Heap-Eigenschaft wiederhergestellt ist.

Die Formel

Rechts = 2 · i + 2

Umstellung:
    i = (Rechts − 2) / 2

Die Variablen

Minimal-Beispiel

Rechtes Kind von Index 4:

Rechts = 2 · 4 + 2
       = 10

Praxis-Beispiele

Beispiel 1 — Bit-Trick

Beide Kinder lassen sich extrem effizient berechnen — moderne CPUs benötigen für 2i+1 und 2i+2 nur je eine LEA-Instruktion:

Links  = (i << 1) | 1     // 2i + 1
Rechts = (i << 1) + 2     // 2i + 2

Beispiel 2 — Auswahl des kleineren Kindes

Sift-Down in Min-Heap der Größe n bei Position i:

Links  = 2·i + 1
Rechts = 2·i + 2
if Rechts < n und A[Rechts] < A[Links]:
    min = Rechts
else:
    min = Links

Beispiel 3 — Letztes Element mit rechtem Kind

In einem Heap mit n = 100 Elementen: existiert das rechte Kind von Index 48?

Rechts = 2 · 48 + 2 = 98
98 < 100 ?  → ja
⇒ Knoten 48 hat sowohl linkes (97) als auch rechtes (98) Kind.
Knoten 49 dagegen hätte Rechts = 100 ≥ 100 → nur linkes Kind.