Was ist Binärer Heap (Binary Heap)?

Vollständiger Binärbaum, in dem der Wert jedes Elternknotens größer oder gleich (Max-Heap) bzw. kleiner oder gleich (Min-Heap) den Werten seiner Kinder ist. Er lässt sich in einem Array speichern: Liegt die Wurzel in a[0], sind die Kinder von a[i] die Elemente a[2i+1] und a[2i+2]. Das Lesen des Maximums (Minimums) kostet O(1), Einfügen und Entnehmen O(log n); verwendet wird er für Prioritätswarteschlangen und Heapsort.

Japanische Bezeichnung: 二分ヒープ

„Binärer Heap (Binary Heap)“ kommt in 1 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Binärer Heap (Binary Heap)

Ein binärer Heap wird mit der Wurzel in a[0] in einem Array a[0], a[1], a[2], … gespeichert, wobei jede Ebene von oben beginnend von links nach rechts aufgefüllt wird. Welches sind die Kinder und der Elternknoten von a[4]?

AKinder a[9] und a[10], Elternknoten a[1]
BKinder a[8] und a[9], Elternknoten a[2]
CKinder a[9] und a[10], Elternknoten a[2]

Antwort und Erläuterung anzeigen

Antwort: A. Kinder a[9] und a[10], Elternknoten a[1]

Liegt die Wurzel in a[0], sind die Kinder von a[i] die Elemente a[2i+1] und a[2i+2], und der Elternknoten ist a[(i−1) ÷ 2, abgerundet]. Für i = 4 sind die Kinder a[9] und a[10], und der Elternknoten ist a[(4−1) ÷ 2] = a[1]. Liegt die Wurzel in a[1], sind die Kinder a[2i] und a[2i+1] und der Elternknoten a[i ÷ 2]; es ist daher wichtig zu prüfen, welche Konvention gilt. Da ein Heap ein vollständiger Binärbaum ist, lässt er sich ohne Zeiger in einem Array speichern, und Eltern und Kinder werden allein durch Indexrechnung gefunden.

Fragen mit „Binärer Heap (Binary Heap)“ (1)

Ein binärer Heap wird mit der Wurzel in a[0] in einem Array a[0], a[1], a[2], … gespeichert, wobei jede Ebene von oben beginnend von links nach rechts aufgefüllt wird. Welches sind die Kinder und der Elternknoten von a[4]?

Was ist Binärer Heap (Binary Heap)?

Jetzt üben: Fragen zu Binärer Heap (Binary Heap)

Ein binärer Heap wird mit der Wurzel in a[0] in einem Array a[0], a[1], a[2], … gespeichert, wobei jede Ebene von oben beginnend von links nach rechts aufgefüllt wird. Welches sind die Kinder und der Elternknoten von a[4]?

Fragen mit „Binärer Heap (Binary Heap)“ (1)

Verwandte Begriffe