Ein Max-Heap, in dem der Wert jedes Elternknotens mindestens so groß ist wie die Werte seiner Kinder, wird in einem Array mit der Wurzel in a[0] gespeichert. Zum Heap 50, 30, 40, 10, 20, 35 wird 45 hinzugefügt, indem es ans Ende gesetzt und dann mit seinem Elternknoten vertauscht wird, solange es größer als dieser ist. Wie sieht das resultierende Array aus?

Antwort: C. 50, 30, 45, 10, 20, 35, 40

45 wird in a[6] gesetzt, dessen Elternknoten a[(6−1) ÷ 2] = a[2] = 40 ist. Wegen 45 > 40 werden beide vertauscht, und 45 rückt nach a[2]. Der nächste Elternknoten a[0] = 50 ist größer als 45, daher endet der Vorgang mit 50, 30, 45, 10, 20, 35, 40. Vertauschungen finden höchstens so oft statt, wie der Baum hoch ist; das Einfügen kostet daher O(log n), und das Entnehmen des Maximums ebenfalls O(log n). Aus diesem Grund werden binäre Heaps häufig zur Implementierung von Prioritätswarteschlangen verwendet.