Aufgabe a)
Fügen Sie die folgenden Zahlen 5,8,3,9,2,4,5,2 der Reihe nach in einen Heap - bestes sei das Minimum - in Binärbaumdarstellung ein.

Im folgenden Bild ist der Baum gezeichnet, der nach Einfügung der ersten sechs Elemente entstanden ist. Dann wird das Element 2 an die freie Stelle in der letzten Schicht gesetzt. Nur der erste freie Platz links in der letzten Schicht ist die Stelle wo ein neues Element eingefügt werden kann. Dort steht es - wie auch hier - meistens an einer falschen Stelle. Es muß im Austausch mit seinem Vorgänger an die richtige Stelle gebracht werden. Hier endet das nach dem ersten Austausch. Allgemein kann sich der Austausch bis zur Wurzel durchziehen.

Aufgabe b)
Betrachten Sie den Heap aus Aufgabe a) und entfernen Sie darin dreimal das jeweils beste Element.

Ausgehend vom Baum mit den sieben Elementen wird im folgenden Bild die Wurzel mit dem Wert 2 entfernt, indem an diese Stelle das letzte Element der letzten Schicht gesetzt wird und dieses letzte Element aus der Baumstruktur entfernt wird. Das Element, das jetzt an der Wurzel steht ist im Regelfall an falscher Stelle. Es wird jetzt "gesenkt". Das Ergebnis ist der dritte Baum in diesem Bild. Der vierte Baum zeigt das zweite Löschen und der letzte Baum das Endergebnis nach dem dritten Löschen.

Aufgabe c)
i)    Ist ein Heap gleichzeitig auch ein binärer Suchbaum ?
ii)   Ist ein binärer Suchbaum auch gleichzeitig ein Heap ?

Beide Fragen sind zu verneinen. Nur bei Extremfällen mit 1 oder 2 Elementen kann ein Heap auch ein binärer Suchbaum sein. Schon ein zweielementiger binärer Suchbaum kann kein Heap mehr sein. Die Ordnungsprinzipien beider Datenstrukturen sind ganz verschieden. Das folgende Beispiel zeigt entsprechende Besipielbäume.