Heap Eltern-Index

Worum geht es?

Ein Binär-Heap wird in der Praxis als Array gespeichert — ganz ohne Pointer. Die Eltern-Kind-Beziehung ergibt sich rein arithmetisch aus dem Index: das Elternelement zu Index i liegt bei ⌊(i − 1) / 2⌋, das linke Kind bei 2i + 1, das rechte bei 2i + 2.

Diese kompakte Repräsentation ist die Grundlage von Heapify, Heap-Sort, Priority-Queues und dem Dijkstra-Algorithmus. Sie spart den Pointer-Overhead eines klassischen Baumes und nutzt die Cache-Lokalität moderner CPUs optimal aus.

Die Formel

Eltern = ⌊(i − 1) / 2⌋

Umstellung (linkes Kind aus Eltern):
    i = 2 · Eltern + 1

Die Variablen

Minimal-Beispiel

Eltern des Elements an Index 7:

Eltern = ⌊(7 − 1) / 2⌋
       = ⌊3⌋
       = 3

Praxis-Beispiele

Beispiel 1 — Heap-Skizze

Indizes und Eltern eines Min-Heaps mit 7 Elementen:

            [0]
           /     \
        [1]       [2]
        / \       / \
      [3] [4]   [5] [6]

i | Eltern
──┼───────
0 |   —
1 |   0
2 |   0
3 |   1
4 |   1
5 |   2
6 |   2

Beispiel 2 — Sift-Up nach Insert

Wird ein neues Element an Position 12 eingefügt, läuft Sift-Up so:

i = 12 → Eltern = ⌊11/2⌋ = 5
i =  5 → Eltern = ⌊ 4/2⌋ = 2
i =  2 → Eltern = ⌊ 1/2⌋ = 0
i =  0 → Wurzel erreicht
⇒ max. 4 Vergleiche.

Beispiel 3 — Heap-Size aus Letztem-Eltern-Index

Bei einem Heap mit n Elementen ist der letzte Knoten mit Kindern bei Index ⌊n/2⌋ − 1. Für n = 100:

last_parent = ⌊100 / 2⌋ − 1
            = 49
⇒ Heapify startet bei i = 49 und läuft rückwärts bis 0.