Nächste Seite: Union-Find-Wälder Aufwärts: Hauptseite Algorithmen Vorherige Seite: Ungerichtete Graphen Inhalt

Unterabschnitte

Minimumheap

Darstellung durch Arrays

Array[1]	:	Wurzel
Array[2i]	:	linker Sohn des Knotens mit der Nummer i
Array[2i+1]	:	rechter Sohn des Knotens mit der Nummer i

Einfügen

Einfügen an der ersten möglichen Position. Danach wird der Knoten mit dem Vater solange getauscht, bis der Vater kleiner als der Vorgängerknoten ist.

Löschen, in dem wir den zu löschenden Knoten mit dem letzten Knoten im Baum vertauschen und dann wegnehmen. Der vertauschte Knoten muß solange mit einem Sohn verglichen werden, bis er kleiner als beide Söhne ist. Dabei muß immer mit dem kleineren der beiden Söhne getauscht werden.

Heapsort

Algorithmus

Heapsort kann durchgeführt werden, indem wir immer das oberste Element entnehmen und danach die Minimumeigenschaften mit dem Algorithmus für das Löschen wiederherstellen.
Dabei kann der Heap zuerst geschrieben werden, indem die Hälfte der Zahlen direkt in den hinteren Teil des Arrays für den Heap kopiert werden. Dann kann immer das Array von hinten mit einem Vater aufgefüllt werden, der dann eventuell abgesenkt wird.

Laufzeit

Für das Absenken im Baum benötigen wir die Laufzeit $O(\log n)$ . Da wir dies

mal für alle Elemente, die wir nacheinander dem Heapbaum in der sortierten Reihenfolge entnehmen, tun müssen, erhalten wir die Laufzeit $O(n\log n)$ . Diese Laufzeit wird auch benötigt, um den Baum vorher aufzubauen. Also erhalten wir insgesamt $O(n\log(n))$ .

Nächste Seite: Union-Find-Wälder Aufwärts: Hauptseite Algorithmen Vorherige Seite: Ungerichtete Graphen Inhalt