imported>Leyo: Layout

2025-04-16T21:46:23Z

Layout

Neue Seite

'''BottomUp-Heapsort''' ist ein [[Sortierverfahren|Sortieralgorithmus]], der u. a. [[1990]] von [[Ingo Wegener]] vorgestellt wurde und im Durchschnitt besser als [[Quicksort]] arbeitet,
falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von [[Heapsort]], die vor allem zur Sortierung sehr großer Datenmengen geeignet ist, wenn (im Vergleich zu den notwendigen Vertauschungsoperationen) ein relativ hoher Aufwand pro Vergleichsoperation erforderlich ist.

Diese Variante wurde allerdings bereits [[1986]] von Svante Carlsson analysiert,
der letztlich eine weitere Variante fand, die sogar eine [[Zeitkomplexität|worst-case]]-Laufzeit von nur ''n'' log ''n'' + O(''n '' log log ''n'') Vergleichen hat. Entdeckt wurde dieser Bottom-Up-Heapsort bereits von [[Robert Floyd|Robert W Floyd]] (bei einer Überarbeitung des ursprünglichen
Heapsorts von Williams), der aber das Laufzeitverhalten dieser Variante nicht beweisen konnte.

Er benötigt zum Sortieren einer Folge von n Schlüsseln
im schlechtesten Fall nur 1,5 ''n'' log ''n'' + 2''n'' Schlüsselvergleiche.
Im Durchschnittsfall benötigt BottomUp-Heapsort nur ''n'' log ''n'' + O(''n'') Schlüsselvergleiche.

== Prinzip der Sortierung ==

Beim Sortieren mit normalem Heapsort finden beim Absenken eines Elements zwei Vergleiche pro Ebene statt:

# Welcher der beiden Nachfolgeknoten des abzusenkenden Elements ist größer?
# Ist der nun bestimmte Nachfolgeknoten größer als das abzusenkende Element?

Nachdem ein [[Binärbaum]] zur Hälfte aus [[Blatt (Graphentheorie)|Blättern]] besteht und zudem beim Sortieren ehemalige Blätter mit ohnehin schon eher niedrigen Werten abgesenkt werden, ist es wahrscheinlich, dass ein Element bis zur Blattebene oder in deren Nähe abgesenkt werden muss. Deshalb kann es lohnend sein, auf den zweiten Vergleich zu verzichten und auf Verdacht bis zur Blattebene abzusenken.

In einem zweiten Schritt wird dann rückwärts überprüft, wie weit das Element wieder angehoben werden muss. Im günstigsten Fall (sehr große Felder mit nur wenigen [[Dublette (Datenbank)|Dubletten]]) kann dabei fast die Hälfte der insgesamt nötigen Vergleiche bei mäßigem Zusatzaufwand eingespart werden.

Weniger geeignet ist BottomUp-Heapsort zur Sortierung kleinerer Felder mit einfacher numerischer Vergleichsoperation und dann, wenn im Feld sehr viele Elemente gleichwertig sind (dann stimmt die Annahme nicht, dass meist bis in die Nähe der Blattebene abgesenkt werden muss).

== Algorithmus ==

Konkret wird der Heapsort-Algorithmus, was das Absenken betrifft, wie folgt verändert:

Zunächst wird der Pfad, in welchem das Wurzelelement versenkt werden soll, bestimmt. Dies geschieht durch die Ermittlung des jeweils größten Kindes (Pfad maximaler Kinder). Danach wird dieser bestimmte Pfad von unten nach oben (vom Blatt in Richtung Wurzel) durchlaufen. Hierbei wird bei jedem besuchten Knoten verglichen, ob er größer als das abzusenkende Wurzelelement ist. Ist dem so, wird das Wurzelelement an die Position des zuletzt besuchten Knotens kopiert und vorher der restliche Pfad um eine Ebene nach oben verschoben.

Alternativ kann man auch die Verschiebung von vornherein auf Verdacht bis zur Blattebene durchführen und später – soweit notwendig – wieder rückgängig machen. Wo Kopien relativ günstig durchgeführt werden können (weil etwa nur ein [[Zeiger (Informatik)|Zeiger]] kopiert wird), kann das insgesamt vorteilhaft sein.

== Beispiel ==

'''Heap''': [9, 23, 24, 20, 18, 14, 17, 13, 15, 11, 10, 5, 7, 3, 2]

'''Baumstruktur:'''

[[Datei:Bottom-Up-Heapsort 01.svg|mini|ohne]]

Das Element '''9''' muss abgesenkt werden, da es kleiner als mindestens ein Nachfolgeknoten ist.
Es wird als erstes der Pfad der maximalen Kinder (ausgehend von der Wurzel) bestimmt. Es ergibt sich also '''9 - 24 - 17 - 3'''.
Der Algorithmus durchläuft diesen Pfad nun von unten nach oben, also '''3 → 17 → 24 → 9'''. Nun wird der Pfad vom Blattknoten '''(3)''' beginnend solange durchlaufen, bis sich ein Knoten findet, der größer als '''9''' ist. Der Durchlauf endet folglich bei '''17'''. Nun werden alle Knoten ab '''17''' bis zum Nachfolgeknoten der Wurzel '''(= 17 → 24)''' um eine Ebene nach oben und der Knoten '''9''' an die Position von '''17''' verschoben. Folglich ändern '''17''' und '''24''' als Nachfolgeknoten und '''9''' als Wurzelknoten ihren Platz.

'''Heap''': [24, 23, 17, 20, 18, 14, 9, 13, 15, 11, 10, 5, 7, 3, 2]

'''Baumstruktur:'''

{{Mehrere Bilder
| align = left
| Richtung = horizontal
| Bild1 = Bottom-Up-Heapsort 02.svg
| Untertitel1 =
| Breite1 = 250
| Bild2 = Bottom-Up-Heapsort 03.svg
| Untertitel2 =
| Breite2 = 250
}}
<div style="clear:both"></div>

== Implementierung ==

Einfache Beispielsimplementierung in [[Varianten der Programmiersprache C#C99|C99]]:

<syntaxhighlight lang="C">
int heapsort_bu( int data[], int n ) // zu sortierendes Feld und seine Länge
{
int val, parent, child;
int root= n >> 1; // erstes Blatt im Baum
int count= 0; // Zähler für Anzahl der Vergleiche

for ( ; ; )
{
if ( root ) { // Teil 1: Konstruktion des Heaps
parent= --root;
val= data[root]; // zu versickernder Wert
}
else
if ( --n ) { // Teil 2: eigentliche Sortierung
val= data[n]; // zu versickernder Wert vom Heap-Ende
data[n]= data[0]; // Spitze des Heaps hinter den Heap in
parent= 0; // den sortierten Bereich verschieben
}
else // Heap ist leer; Sortierung beendet
break;

while ( (child= (parent + 1) << 1) < n ) // zweites (!) Kind;
{ // Abbruch am Ende des Heaps
if ( ++count, data[child-1] > data[child] ) // größeres Kind wählen
--child;

data[parent]= data[child]; // größeres Kind nach oben rücken
parent= child; // in der Ebene darunter weitersuchen
}

if ( child == n ) // ein einzelnes Kind am Heap-Ende
{ // ist übersprungen worden
if ( ++count, data[--child] >= val ) { // größer als der zu versick-
data[parent]= data[child]; // ernde Wert, also noch nach oben
data[child]= val; // versickerten Wert eintragen
continue;
}

child= parent; // 1 Ebene nach oben zurück
}
else
{
if ( ++count, data[parent] >= val ) { // das Blatt ist größer als der
data[parent]= val; // zu versickernde Wert, der damit
continue; // direkt eingetragen werden kann
}

child= (parent - 1) >> 1; // 2 Ebenen nach oben zurück
}

while ( child != root ) // maximal zum Ausgangspunkt zurück
{
parent= (child - 1) >> 1; // den Vergleichswert haben wir bereits
// nach oben verschoben
if ( ++count, data[parent] >= val ) // größer als der zu versickernde
break; // Wert, also Position gefunden

data[child]= data[parent]; // Rückverschiebung nötig
child= parent; // 1 Ebene nach oben zurück
}

data[child]= val; // versickerten Wert eintragen
}

return count;
}
</syntaxhighlight>

Zu Vergleichszwecken gibt die Funktion die Anzahl der durchgeführten Vergleiche zurück.

== Literatur ==
* J. W. J. Williams: ''Algorithm 232 – Heapsort''. In: ''Communications of the ACM'', 1964, 7(6), S. 347–348.
* Robert W. Floyd: ''Algorithm 245 – Treesort 3''. In: ''Communications of the ACM'', 1964, 7(12), S. 701.
* S. Carlsson: ''HEAPS''. Doctoral dissertation, Lund Univ., Sweden 1986.
* Svante Carlsson: ''Average-case results on heapsort''. In: ''BIT'', 27, 1987, no.1, S. 2–17.
* Ingo Wegener: ''BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)''. 15th International Symposium on Mathematical Foundations of Computer Science (MFCS ’90) Banská Bystrica, 1990. In: ''Theoret. Comput. Sci.'', 118, 1993, no. 1, S. 81–98.

[[Kategorie:Sortieralgorithmus]]

Bottom-Up-Heapsort - Versionsgeschichte

imported>Leyo: Layout