• Increase font size
  • Default font size
  • Decrease font size

Heapsort

Drucken

 Robert W. Floyd

Eine andere Anwendung die auf der Verwendung von Binärbäumen basiert, ist Heapsort, ein vergleichsweise effizientes Sortierverfahren nach Robert W. Floyd. Ausgangspunkt für Heapsort ist die Interpretation eines Feldes als Baum. Die Elemente des Feldes werden in einen Binärbaum ebenenweise eingelesen. Die so entstehenden Einträge oder Markierungen werden indiziert, Wurzel 0, Ebene 1, die Indizes 1 und 2 und so fort. Die erste Stufe des Heapsort besteht nun darin einen Heap zu bilden. Dabei ist folgende Invariante herzustellen.

 

Invariante  -  Element(x)  >= MAX [Element(2x), Element(2x+1)]   x..Index

 

Die zweite Stufe dient der eigentlichen Sortierung. Dies geschieht in der Weise, dass das letzte Element mit dem Element an der Wurzel getauscht wird. Damit gelangt das bis dato größte Element an das Ende des Feldes und ist sortiert, wird also beim weiteren Vorgang nicht berücksichtigt. Das nun in der Wurzel stehende Element ist nicht zwingend das größte, gehört dort also nicht unbedingt hin. Vergleichbar dem Aufbau des Heap beginnt nun ein Sinkvorgang, der in der Regel analog implementiert wird und das Element im Baum an die richtige Stelle transportiert. Das rekursive Anwenden des Vorganges vergrößert das sortierte Feld und verkleinert den Baum. Ist der Baum der leere Baum, ist das Feld sortiert. Nachfolgendes Applet stellt den Vorgang stark verkürzt dar. Eine ausführliche Beschreibung einiger Baumeigenschaften, sowie des Heapsorts findet sich weiter unten.

 

    Script zu Baumstrukturen

 

 

(c) g-ymnasium.de 2006 - 2013 + Administrator