Heapsort
Ein Baum ist ein gerichteter Graph, d.h. eine Struktur bestehend aus Knoten und gerichteten Kanten (Pfeile) zwischen Knoten, so daß gilt:
1) genau ein Knoten besitzt keine eingehende Kante (Wurzel)
2) alle übrigen Knoten besitzen genau 1 eingehende Kante.
Ein Baum heißt Binärbaum, wenn alle Knoten höchstens 2 ausgehende Kanten besitzen (Knoten ohne ausgehende Kanten heißen Blätter) und wenn zwischen dem linken und re. Sohn eines Knotens unterschieden wird.
Ein Binärbaum heißt vollständig, wenn es keinen Binärbaum derselben Tiefe mit mehr Knoten gibt. Die Tiefe ist die Länge des längsten gerichteten Pfades in einem Baum.
Definition: Ein Heap H (deutsch: Halde) ist ein Baum, für den folgendes gilt:
1) Sei n die Tiefe von H. Bis zur Tiefe n-1 ist H vollständiger Binärbaum.
2) Die Blätter der Tiefe n sind linksbündig im Baum angeordnet.
3) Knoten sind items. Der Schlüssel jedes Knotens ist größer als die Schlüssel seiner direkten Nachfolger (Söhne).