Heapsort ist ein Vergleich-basierter Sortieren-Algorithmus, um eine sortierte Reihe (oder Liste) zu schaffen, und ist ein Teil der Auswahl-Sorte-Familie. Obwohl etwas langsamer in der Praxis auf den meisten Maschinen als eine gut durchgeführte Schnellsortierung es im Vorteil eines günstigeren Grenzfalls O ist (n, loggen n) Durchlaufzeit. Heapsort ist ein Algorithmus im Platz, aber ist nicht eine stabile Sorte.

Übersicht

Heapsort beginnt durch das Gebäude eines Haufens aus der Datei, und dann das Entfernen des größten Artikels und das Stellen davon am Ende der teilweise sortierten Reihe. Nach dem Entfernen des größten Artikels baut es den Haufen wieder auf, entfernt den größten restlichen Artikel, und legt es in die folgende offene Position vom Ende der teilweise sortierten Reihe. Das wird wiederholt, bis es keine im Haufen verlassenen Sachen gibt und die sortierte Reihe voll ist. Elementare Durchführungen verlangen, dass zwei Reihe - ein den Haufen und den anderen hält, die sortierten Elemente zu halten.

Heapsort fügt die Eingangslistenelemente in eine binäre Haufen-Datenstruktur ein. Der größte Wert (in einem Max-Haufen) oder der kleinste Wert (in einem Minute-Haufen) werden bis zu niemandem herausgezogen, bleiben die Werte, die in der sortierten Ordnung herausziehen worden sind. Der invariant des Haufens wird nach jeder Förderung bewahrt, so sind die einzigen Kosten die der Förderung.

Während der Förderung ist der einzige erforderliche Raum, der den Haufen versorgen musste. Um unveränderlichen Raum oben zu erreichen, wird der Haufen im Teil der noch nicht sortierten Eingangsreihe versorgt. (Die Lagerung von Haufen als Reihe wird am Binären heap#Heap Durchführung schematisch dargestellt.)

Heapsort verwendet zwei Haufen-Operationen: Einfügung und Wurzelauswischen. Jede Förderung legt ein Element in die letzte leere Position der Reihe. Das restliche Präfix der Reihe versorgt die unsortierten Elemente.

Schwankungen

• Die wichtigste Schwankung zur einfachen Variante ist eine Verbesserung durch R. W. Floyd, der in der Praxis ungefähr eine 25-%-Geschwindigkeitsverbesserung durch das Verwenden nur eines Vergleichs in jedem geführten siftup gibt, dem von einem siftdown für das ursprüngliche Kind gefolgt werden muss. Außerdem ist es eleganter, um zu formulieren. Die natürliche Weise von Heapsort, Arbeiten an Indizes von 1 bis zur Zahl von Sachen mit einem Inhaltsverzeichnis zu versehen. Deshalb sollte die Anfang-Adresse der Daten solch ausgewechselt werden, dass diese Logik durchgeführt werden kann, unnötig +/-1 Ausgleiche im codierten Algorithmus vermeidend.
• Dreifältiger heapsort verwendet einen dreifältigen Haufen statt eines binären Haufens; d. h. jedes Element im Haufen hat drei Kinder. Es ist zum Programm mehr kompliziert, aber tut eine unveränderliche Zahl von Zeiten weniger Tausch und Vergleich-Operationen. Das ist, weil jeder Schritt in der Verschiebungsoperation eines dreifältigen Haufens drei Vergleiche und einen Tausch verlangt, wohingegen in einem binären Haufen zwei Vergleiche und ein Tausch erforderlich sind. Der dreifältige Haufen tut zwei Schritte in kürzerer Zeit, als der binäre Haufen für drei Schritte verlangt, der den Index mit einem Faktor 9 statt des Faktors 8 von drei binären Schritten multipliziert. Dreifältiger heapsort ist um ungefähr 12 % schneller als die einfache Variante von binärem heapsort.
• Der smoothsort Algorithmus ist eine Schwankung von heapsort, der von Edsger Dijkstra 1981 entwickelt ist. Wie heapsort ist smoothsort's ober gebunden O (n loggen n). Der Vorteil von smoothsort besteht darin, dass er näher an O (n) Zeit kommt, wenn der Eingang bereits zu einem gewissen Grad sortiert wird, wohingegen heapsort Durchschnitte O (n loggen n), unabhängig von der Initiale sortierter Staat. Wegen seiner Kompliziertheit wird smoothsort selten verwendet.
• Levcopoulos und Petersson beschreiben eine Schwankung von heapsort, der auf einem Kartesianischen Baum gestützt ist, der kein Element zum Haufen hinzufügt, bis kleinere Werte an beiden Seiten davon bereits in die sortierte Produktion eingeschlossen worden sind. Da sie sich zeigen, kann diese Modifizierung den Algorithmus der Sorte schneller erlauben als O (n loggen n) für Eingänge, die bereits fast sortiert werden.
• Ingo Wegener beschreibt von unten nach oben Version von heapsort, der siftdown durch eine Alternative ersetzt, die den Grenzfall von o (2n Klotz (n)) zu o (1.5n Klotz (n)) reduziert und gefordert wird, besser zu leisten, als einige Versionen der Schnellsortierung.

Vergleich mit anderen Sorten

Heapsort bewirbt sich in erster Linie mit der Schnellsortierung, ein anderer sehr effizienter allgemeiner Zweck fast in Platz Vergleich-basierter Sorte-Algorithmus.

Schnellsortierung ist normalerweise, wegen des besseren Verhaltens des geheimen Lagers und der anderen Faktoren etwas schneller, aber die Grenzfall-Laufzeit für die Schnellsortierung ist O (n), der für große Dateien unannehmbar ist und gegeben genug Kenntnisse der Durchführung absichtlich ausgelöst werden kann, ein Sicherheitsrisiko schaffend. Sieh Schnellsortierung für eine ausführliche Diskussion dieses Problems und mögliche Lösungen.

So, wegen des O (n loggen n), ober hat zur Laufzeit von heapsort gebunden, und unveränderlich ober hat zu seiner Hilfslagerung gebunden, eingebettete Systeme mit Echtzeiteinschränkungen oder Systeme, die mit der Sicherheit häufig betroffen sind, verwenden heapsort.

Heapsort bewirbt sich auch mit der Verflechtungssorte, die dieselben Zeitgrenzen hat, aber Ω (n) Hilfsraum verlangt, wohingegen heapsort nur einen unveränderlichen Betrag verlangt. Heapsort läuft auch normalerweise schneller in der Praxis auf Maschinen mit kleinen oder langsamen geheimen Datenlagern. Andererseits hat Verflechtungssorte mehrere Vorteile gegenüber heapsort:

• Wie Schnellsortierung hat die Verflechtungssorte auf der Reihe beträchtlich bessere Datenleistung des geheimen Lagers, häufig heapsort auf einem modernen Tisch-PC überbietend, weil es auf die Elemente in der Ordnung zugreift.
• Verflechtungssorte ist eine stabile Sorte.
• Verflechtungssorte parallelizes besser; der trivialste Weg der Parallelizing-Verflechtungssorte erreicht in der Nähe von der geradlinigen Beschleunigung, während es keinen offensichtlichen Weg zu parallelize heapsort überhaupt gibt.
• Verflechtungssorte kann leicht angepasst werden, um auf verbundenen Listen (mit O (1) Extraraum) und sehr großen Listen zu funktionieren, die auf zum Zugang langsamen Medien wie Plattenlagerung versorgt sind, oder Netz hat Lagerung beigefügt. Heapsort verlässt sich stark auf den zufälligen Zugang, und seine schlechte Gegend der Verweisung macht es sehr langsam auf Medien mit langen Zugriffszeiten. (Bemerken Sie: Heapsort kann auch auf doppelt verbundene Listen mit nur O (1) Extraraum oben angewandt werden)

Introsort ist eine interessante Alternative zu heapsort, der Schnellsortierung und heapsort verbindet, um Vorteile von beiden zu behalten: Grenzfall-Geschwindigkeit von heapsort und durchschnittliche Geschwindigkeit der Schnellsortierung.

Pseudocode

Der folgende ist die "einfache" Weise, den Algorithmus im Pseudocode durchzuführen. Reihe ist bei Nullpunkteinstellung, und Tausch wird verwendet, um zwei Elemente der Reihe auszutauschen. Bewegung bedeutet 'unten' von der Wurzel zu den Blättern, oder von niedrigeren Indizes bis höher. Bemerken Sie, dass während der Sorte das größte Element an der Wurzel des Haufens an [0] ist, während am Ende der Sorte das größte Element in [Ende] ist.

fungieren Sie heapSort (a, Zählung) ist

Eingang: Eine nicht eingeordnete Reihe der Länge zählt auf

(legen Sie zuerst in die Max-Haufen-Ordnung)

heapify (a, Zählung)

Ende: = Punkt der Klagebegründung 1//auf Sprachen mit der Reihe bei Nullpunkteinstellung sind die Kinder 2*i+1 und 2*i+2

während Ende> 0 tut

(tauschen Sie die Wurzel (maximaler Wert) vom Haufen mit dem letzten Element des Haufens)

Tausch ([Ende], [0])

(vermindern Sie die Größe des Haufens durch denjenigen, so dass der vorherige Max-Wert wird

bleiben Sie in seinem richtigen Stellen)

Ende: = Ende - 1

(stellen Sie den Haufen zurück in der Max-Haufen-Ordnung)

siftDown (a, 0, Ende)

fungieren Sie heapify (a, Zählung) ist

(Anfang wird der Index in vom letzten Elternteilknoten zugeteilt)

Anfang: = (Zählung - 2) / 2

während Anfang  0 tut

(durchrieseln Sie unten der Knoten am Index fangen zum richtigen solchem Platz dass alle Knoten unter an

der Anfang-Index ist in der Haufen-Ordnung)

siftDown (a, fangen Sie Punkt der Klagebegründung 1 an)

Anfang: = Anfang - 1

(nachdem, unten die Wurzel siebend, alle Knoten/Elemente in der Haufen-Ordnung sind)

fungieren Sie siftDown (a, fangen Sie an, Ende) ist

Eingang: Ende vertritt die Grenze wie weit unten der Haufen

zu durchrieseln.

Wurzel: = fangen an

während Wurzel * 2 + 1 -Ende tut (Während die Wurzel mindestens ein Kind hat)

Kind: = wurzeln * 2 + 1 (root*2 + 1 Punkte dem linken Kind) ein

Tausch: = Wurzel (geht das Kind nach, um mit zu tauschen)

(überprüfen Sie, ob Wurzel kleiner ist als linkes Kind)

wenn [Tausch]

Das kann gegenintuitiv seitdem mit einem flüchtigen Blick scheinen, es ist offenbar, dass der erstere nur halb so viel Anrufe zu seiner logarithmisch-maligen durchrieselnden Funktion macht wie die Letzteren; d. h. sie scheinen, sich nur durch einen unveränderlichen Faktor zu unterscheiden, der nie einen Einfluss auf asymptotische Analyse hat.

Um die Intuition hinter diesem Unterschied in der Kompliziertheit zu ergreifen, bemerken Sie, dass die Zahl des Tausches, der während irgendwelcher SiftUp-Anruf-Zunahmen mit der Tiefe des Knotens vorkommen kann, auf dem der Anruf gemacht wird. Der Kernpunkt ist, dass es viele (exponential viele) "tiefere" Knoten gibt als, gibt es "seichte" Knoten in einem Haufen, so dass siftUp seine volle logarithmische Laufzeit auf der ungefähr geradlinigen Zahl von Anrufen haben kann, die auf den Knoten an oder in der Nähe vom "Boden" des Haufens gemacht sind. Andererseits, die Zahl des Tausches, der während irgendwelcher SiftDown-Anruf-Abnahmen als die Tiefe des Knotens vorkommen kann, auf dem der Anruf Zunahmen gemacht wird. So, wenn der "siftDown" heapify beginnt und siftDown auf dem Boden und den zahlreichsten Knotenschichten nennt, wird jeder durchrieselnde Anruf, höchstens, mehreren Tausch übernehmen, der der "Höhe" (vom Boden des Haufens) des Knotens gleich ist, auf dem der durchrieselnde Anruf gemacht wird. Mit anderen Worten wird ungefähr Hälfte der Anrufe siftDown höchstens nur einen Tausch haben, dann über ein Viertel der Anrufe wird höchstens zwei Tausch usw. haben.

Der heapsort Algorithmus selbst hat Zeitkompliziertheit mit jeder Version von heapify.

fungieren Sie heapify (a, Zählung) ist

(Ende wird der Index des ersten (linken) Kindes der Wurzel zugeteilt)

Ende: = 1

während Ende

Elternteil: = Fußboden ((Kind - 1) ÷ 2)

wenn ein [Elternteil-]

• J. W. J. Williams. Algorithmus 232 - Heapsort, 1964, Kommunikationen des ACM 7 (6): 347-348.
• Robert W. Floyd. Algorithmus 245 - Treesort 3, 1964, Kommunikationen des ACM 7 (12): 701.
• Svante Carlsson, Ergebnisse des Durchschnittlichen Falls auf heapsort, 1987, hat 27 (1) GEBISSEN: 2-17.
• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 3: Sortierend und Suche, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89685-0. Seiten 144-155 des Abschnitts 5.2.3: Das Sortieren durch die Auswahl.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Kapitel 6 und 7 Beziehungsweise: Heapsort und Priority Queues
• Ein PDF von ursprünglichem Papier von Dijkstra auf Smoothsort
• Haufen und Heapsort Tutorenkurs durch David Carlson, Universität von St. Vincent
• Haufen von Kenntnissen

Außenverbindungen

• Belebte Sortieren-Algorithmen: Haufen-Sorte - grafische Demonstration und Diskussion der Haufen-Sorte
• Lernsoftware auf Heapsort von Univ. Oldenburg - Mit dem Text, den Zeichentrickfilmen und den interaktiven Übungen
• Das Wörterbuch von NIST von Algorithmen und Datenstrukturen: Heapsort
• Heapsort, der auf 12 Sprachen durchgeführt ist
• Das Sortieren wieder besucht von Paul Hsieh
• Ein grafisches Farbenjava applet, der Experimentieren mit dem anfänglichen Staat erlaubt und Statistik zeigt
• Eine Präsentation von PowerPoint, die wie Haufen-Sorte-Arbeiten demonstriert, der für Pädagogen ist.
• Offene Datenstrukturen - Abschnitt 11.1.3 - Haufen-Sorte