Die Datenstruktur des Heapsortes ist ein Binärbaum. An der “Wurzel” des Baumes befindet sich immer das Element, welches als nächstes benötigt wird. (Min,Max,Priority,etc.) Somit muss beim Einfügen und beim Entfernen eines Elementes der Baum immer wieder sortiert werden. Die Laufzeit ist hierbei asymptotisch und beträgt O(n * log(n)).

 Funktionsweise – Insert

http://www.linux-related.de/coding/sort/pics/heapsort_baum.png

http://www.linux-related.de/coding/sort/pics/heapsort_baum.png

Beim Einfügen werden die Elemente der Reihe nach im Baum an der nächsten freien stelle eingefügt. Das ganze kann wie ein Array interpretiert werden.

[E0,E1,E2,E3,E4,E5,E6….En-2,En-1,En]
Nach dem Einfügen des Elementes wird der Baum neu sortiert. Entscheidend ist hierbei, dass nur der Ast sortiert wird, welcher das neue Element beinhaltet. (Die restlichen Äste sind bereits sortiert und bedürfen keiner Neusortierung)

Grafische Darstellung des Einfügens der Elemente: 8, 2, 3, 4, 6, 1, 3 anhand eines Beispiels. (Wurzelelement soll ein Minimum sein)

12

Im ersten Schritt wird die Acht eingefügt. Es gibt noch keine Elemente zum Vergleichen/vertauschen. Im Schritt 2 wird die zwei an der nächsten freien Stelle eingefügt. Nun wird die zwei mit dem Parent verglichen. Da 2 < 8 müssen diese Elemente vertauscht werden.

3 4

Im Schritt 3 wird die 3 eingefügt. 3 > 2 also muss nichts vertauscht werden. Im Schritt 4 wird die 4 an der nächsten freien Stelle eingefügt. 4 < 8 also werden diese wieder vertauscht.
5 6

Im Schritt 5 wird die 6 hinzugefügt. Keine Vertauschung mit dem Parent 4 nötig. Im Schritt 6 wird 1 an die nächste freie Stelle eingefügt. 1 < 3 somit müssen diese vertauscht werden.

7 8

1 < 2 also werden diese auch noch vertauscht. Im Schritt 6 wird die 3 an die letzte Stelle eingefügt.
3 > 2 somit kein Umtausch nötig.

Funktionsweise – Remove

Das Wurzelelement wird zurückgegeben, das letzte Element an die Wurzelposition gestellt und eine rekursive Sortierung durchgeführt, indem der Parent immer mit den Childs verglichen und bei Bedarf vertauscht wird.

Grafische Darstellung des Entfernens der Elemente 1, 2, 3, 3, 4, 6, 8

1-1 1-2

Im Schritt 1 wird das Wurzelelement zurückgegeben. (1) das letzte Element (3) rückt nach.
Im Schritt 2 wird das nachgerückte Element (3) mit Element (2) vertauscht, da 3 < 2.

1-3 1-4

Die (2) wird im Schritt 3 zurückgegeben. Das letzte Element (3) rückt nach. Es muss im Schritt 3 nichts vertauscht werden, da 2 < 3 && 2 < 4.

1-5 1-6

Die (3) wird im Schritt 4 zurückgegeben. Das letzte Element (6) rückt nach und muss im Schritt 5 mit der (3) vertauscht werden.

1-7 1-8

Schritt 6: Die (3) wird zurückgegeben, (8) rückt nach und muss anschließend im Schritt 7 mit der (4) vertauscht werden.

1-9 1-10

Die (4) wird im Schritt 8 zurückgegeben, die (6) rückt nach und muss im Schritt 9 nicht vertauscht werden.

1-11

Die letzte Zahl ist (8). Nachdem diese zurückgegeben wurde, lautet der Output: 1, 2, 3, 3, 4, 6, 8.

Speicherung

Die Containerelemente (Value + Generic-Container) werden in einem Array gespeichert. Die Länge des Arrays wird automatisch erweitert, sobald ein neues Element die Größe des Arrays überschreiten sollte.

Insert

Abgesehen von der Sortierung, muss auf die Größe des Arrays geachtet werden. Ist die maximale Größe erreicht, so muss der Speicherplatz verdoppelt werden. Auch auf eine NULL Referenz (neues Element) muss geachtet werden.

Remove

Get parent

Nach dem Einfügen wissen wir an welcher Stelle sich das neuste Element befindet. (Size – 1)
Somit haben wir dessen Index, benötigen jedoch den Index des Parents um weitere vergleiche und Vertauschungen vornehmen zu können.

Get right child

Nach dem Entfernen des Wurzelelementes müssen wir auf die Childs mithilfe des Wurzelindexes (0) zugreifen können, um Vergleiche und Umtauschungen vornehmen zu können.

Get left child

Diese Methode ist zwar aufgrund des Methodenaufrufes unperformanter (Interrupt + content switch + calculation + store result + content switch), sieht jedoch ein bisschen ästhetischer aus.

Das Fundament ist mit den oberen Methoden bereits gelegt. Wir können Nodes anlegen, entfernen und auf alle Containerelemente (Parent, Left-Child, Right-Child) zugreifen. Nun folgt die Sortierung. Diese wird in zwei Teile aufgeteilt. Dem Up und Downsort. Wird ein Element eingefügt, (an letzter Stelle) muss von unten (letzte Stelle) nach oben (Wurzelelement) sortiert werden. Wird ein Element entfernt, (Wurzelelement) muss von oben nach unten der Baum sortiert werden.

UpSort

Solange das Parent-Element bei dem Vergleich (compareTo) besser abschneidet ( > 0) als das Child-Element, müssen diese vertauscht werden. Endet der Vergleich jedoch mit (< 0) so kann der Sortiervorgang sofort abgebrochen werden. (Der Ast ist bereits perfekt sortiert)

 DownSort

Vergleiche das Wurzelelement mit seinen Kindern. Ist eines der Kinder im compareTo besser (> 0) so müssen diese vertauscht werden. Nach dem Tausch muss der davon betroffene Ast solange weiter rekursiv sortiert werden, bis beide Kinder bei einem compareTo mit dem Parent mit einem (< 0) abschneiden.

Mein, für die Erklärung, zur Verfügung gestellter Code kann natürlich noch weiter optimiert werden. (Zwischenspeicherung von Ergebnissen, lokale Variablen für aktuelle Größe, weniger Methodenaufrufe etc.)