Ein Heap ist eine spezialisierte Baumdatenstruktur, die die sogenannte Heap-Bedingung erfüllt:
🗼
Wenn P ein Elternknoten von C ist, dann ist der Wert von P größer oder gleich (in einem Max-Heap) bzw. kleiner oder gleich (in einem Min-Heap) als der Wert von C.
Ein Beispiel für einen Max-Heap mit 8 Knoten
Es gibt zwei Haupttypen von Heaps:
Max Heap: Der Wert des Elternknotens ist größer oder gleich dem Wert seiner Kindknoten.
Min Heap: Der Wert des Elternknotens ist kleiner oder gleich dem Wert seiner Kindknoten.
Wir konzentrieren uns auf den Max-Heap, da die meisten Standardbibliotheken für Priority Queues typischerweise einen Max-Heap implementieren. In einem Max-Heap ist das Wurzelelement das größte Element, während die Blätter die kleinsten sind. Es gibt allerdings keine besondere Anordnung bei den Blattknoten. Die einzige Garantie besteht darin, dass der Wert der Wurzel am größten ist und alle Kindknoten kleiner oder gleich diesem Wert sind.
Beachte, dass die letzte Ebene des Heaps immer von links nach rechts aufgefüllt wird. Das heißt, das linke Blatt wird zuerst belegt, und das rechte Blatt zuletzt – wie im oben gezeigten Bild.
Implementation
Ein Heap kann als Array implementiert werden, wobei das erste Element des Arrays den Wurzelknoten darstellt. Da jeder Knoten nur zwei Kindknoten hat, kann man die Indizierung folgendermaßen festlegen:
Das Wurzelelement befindet sich bei Index 1.
Die linken und rechten Kindknoten eines Knotens mit Index i befinden sich bei 2i und 2i+1.
Der Elternknoten eines Elements mit Index i befindet sich bei i // 2.
Der oben abgebildete Heap kann in einer Liste folgendermaßen dargestellt werden:
# Lies einfach jede Zeile aus der Grafik ab und schreibe die Zahlen nebeneinander
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# Oder zur besseren Übersicht
heap = [None, # Wir überspringen Index [0], um eine einfachere Indizierung zu haben
8, # Index [1]
5, 7, # Indizes [2, 3]
1, 1, 6, 3, # Indizes [4, 5, 6, 7]
1] # Index [8]
Challenge: Check if the binary tree is a heap
Gegeben ist ein binärer Baum, der in einem Array von n Zahlen repräsentiert wird (mit der oben genannten Indizierung). Deine Aufgabe ist es zu prüfen, ob dieser Baum die Max-Heap-Bedingung erfüllt.
Input
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ 100 000).
Die nächste Zeile enthält n durch Leerzeichen getrennte Ganzzahlen (), welche die Werte der Elemente im Heap darstellen.
Output
Das Programm soll Yes ausgeben, wenn der binäre Baum die Max-Heap-Bedingung erfüllt, und No, wenn dies nicht der Fall ist.
Examples
Eingabe
Ausgabe
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Explanation
Example 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Example 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
