Daten, die in einem Heap abgelegt werden, müssen sortierbar sein.
Vielfach handelt es sich dabei um Zahlen oder Buchstaben.
Aber auch jeder andere Datentyp, für den die Relationen „größer“ und
„kleiner“ implementiert sind, lassen sich so verwalten.
Damit man bei einem Binärbaum von einem Heap
sprechen kann, müssen zwei Eigenschaften erfüllt sein:
Zum einen die Eigenschaft der „Ordnung“, d.h. der Schlüsselwert
des Vaters ist immer kleiner (oder größer, je nach Implementierung)
als die Schlüsselwerte der Söhne, wobei an die Schlüsselwert, im
Gegensatz zu einem Suchbaum, keine Ansprüche gestellt werden.
Der kleinste (größte) Wert steht also in der Wurzel.
Die zweite Eigenschaft, die erfüllt sein muss, ist die Eigenschaft
der Form.
Diese beiden Eigenschaften stellen sicher, dass kein Knoten weiter
als log n von der Wurzel entfernt ist.
Ein Baum, der als Heap bezeichnet werden soll, muss
links-vollständig sein.
Links-vollständig bedeutet, dass ein Baum der Höhe h bis zur
Höhe h-1 vollständig, d.h. jeder Knoten hat zwei Söhne, sein muss.
Die Knoten der Höhe h liegen so weit links wie möglich. Wenn also
ein Knoten der Höhe h keinen linken Sohn hat, kann er auch keinen
rechten Sohn haben.
So ist außerdem gewährleistet, dass es keine Löcher im Baum gibt.
Aber auch, dass das kleinste (größte) Element leicht auffindbar
ist (Wurzel) und ein effizientes Umsortieren beim Löschen und Einfügen
möglich ist.