Heapify All The Things With Heap Sort
Jemand sagte mir einmal, dass alles Wichtige in der Informatik auf Bäume hinausläuft. Buchstäblich nur Bäume. Wir können sie benutzen, um Dinge zu bauen, Dinge zu analysieren und Dinge zu interpretieren (ja, hier wird vielleicht etwas vorweggenommen, machen Sie sich keine Sorgen, wenn es für Sie noch keinen Sinn ergibt, denn das wird es bald!) Und wir können sie sogar benutzen, um – du hast es erraten! – Dinge zu sortieren.
Ah, sortieren. Wir haben in den letzten Wochen so viel sortiert, aber wir nähern uns jetzt dem Ende unseres Sortierabenteuers. Es ist jedoch unmöglich und unfair, über das Sortieren zu sprechen, ohne auf eine besondere Art des Sortierens einzugehen, bei der die neueste Datenstruktur in unserem Datenstruktur-Werkzeuggürtel zum Einsatz kommt.
Wir haben vor kurzem gelernt, Heaps zu lieben, eine besondere Art von Binärbaum, der einem strengen Regelwerk folgt und zur Implementierung von Dingen wie Prioritätswarteschlangen und Hintergrundjobs verwendet wird. Aber das sind nicht die einzigen Dinge, für die Heaps gut sind. Es stellt sich heraus, dass binäre Heaps oft zu keinem anderen Zweck als zum effizienten Sortieren verwendet werden. Viele Programme verlassen sich auf die Heap-Sortierung, da sie eine der effizientesten Möglichkeiten ist, ein Array zu sortieren. Und da wir nun wissen, was ein Heap ist, können wir versuchen zu verstehen, warum er so gut funktioniert, wenn es um das Problem des Sortierens geht!
Bevor wir uns in die Heap-Sortierung stürzen, sollten wir sicherstellen, dass wir Heaps richtig im Kopf haben. Wir erinnern uns vielleicht daran, dass ein Heap eigentlich nichts anderes ist als ein Binärbaum mit einigen zusätzlichen Regeln, die er befolgen muss: Erstens muss er immer eine Heap-Struktur haben, bei der alle Ebenen des Binärbaums von links nach rechts aufgefüllt werden, und zweitens muss er entweder als Max Heap oder als Min Heap geordnet sein. Für die Zwecke der Heap-Sortierung werden wir uns ausschließlich mit Max-Heaps beschäftigen, bei denen jeder Elternknoten (einschließlich der Wurzel) größer oder gleich dem Wert seiner Kinderknoten ist.
Okay, kommen wir zur Beantwortung der Frage der Stunde: Wie sortiert man mit Heaps? Nun, um diese Frage zu beantworten, müssen wir zunächst verstehen, was ein Heap-Sortieralgorithmus ist!
Ein Heap-Sortieralgorithmus ist eine Sortiertechnik, die sich auf binäre Heap-Datenstrukturen stützt. Da wir wissen, dass Heaps immer einer bestimmten Reihenfolge folgen müssen, können wir uns diese Eigenschaft zunutze machen, um das größte Element mit dem höchsten Wert zu finden und die Elemente nacheinander zu sortieren, indem wir den Wurzelknoten eines Heaps auswählen und ihn an das Ende des Arrays anhängen.
Wir wissen bereits, dass Heap-Sortierung eine effiziente Methode ist, um ein unsortiertes Array zu sortieren; aber was hat ein Array mit einem Heap zu tun? Und wie sortiert man ein Array mit einem Heap? Nun, es gibt drei Schlüsselschritte, wie das in der Praxis funktioniert. Wir werden uns diese in einem Moment genauer ansehen, aber lassen Sie uns zunächst einen kurzen Blick auf diese drei Schritte werfen.
- Zu Beginn haben wir ein unsortiertes Array. Der erste Schritt besteht darin, dieses Array in einen Heap zu verwandeln; in unserem Fall wollen wir es in einen Max Heap verwandeln. Wir müssen also die Daten unseres unsortierten Arrays transformieren und einen Max Heap erstellen. Normalerweise wird dies durch eine einzige Funktion gekapselt, die etwa so heißen könnte:
buildMaxHeap. - Wenn wir unsere Array-Daten in einem Max-Heap-Format haben, können wir sicher sein, dass der größte Wert am Wurzelknoten des Heaps liegt. Denken Sie daran, dass, auch wenn der gesamte Heap nicht sortiert ist, wenn wir unseren Max Heap korrekt und fehlerfrei aufgebaut haben, jeder einzelne Elternknoten in unserem Heap einen größeren Wert hat als seine Kinder. Wir verschieben also den größten Wert – der sich am Wurzelknoten befindet – an das Ende des Heaps, indem wir ihn mit dem letzten Element vertauschen.
- Jetzt befindet sich das größte Element im Heap am letzten Knoten, was großartig ist. Wir wissen, dass es sich an seiner sortierten Position befindet, so dass es vollständig aus dem Heap entfernt werden kann. Aber es gibt noch einen weiteren Schritt: Wir müssen sicherstellen, dass sich das neue Element des Wurzelknotens an der richtigen Stelle befindet! Es ist höchst unwahrscheinlich, dass sich das Element, das wir in die Position des Wurzelknotens verschoben haben, an der richtigen Stelle befindet. Daher verschieben wir das Element des Wurzelknotens nach unten an die richtige Stelle, wobei wir eine Funktion verwenden, die normalerweise so etwas wie
heapify.
heißt, und das ist im Grunde alles! Der Algorithmus wiederholt diese Schritte, bis der Heap nur noch aus einem einzigen Knoten besteht. Zu diesem Zeitpunkt weiß er, dass sich alle Elemente in der unsortierten Anordnung an ihren sortierten Positionen befinden und dass der letzte verbleibende Knoten das erste Element in der sortierten Anordnung sein wird.
Okay, ich weiß, dass ich gesagt habe, dass dies die einzigen drei Schritte der Haufensortierung sind. Aber wenn Ihnen diese drei Schritte verwirrend erscheinen, machen Sie sich keine Sorgen; sie können ziemlich kompliziert und schwer zu verstehen sein, bis Sie sie in Aktion sehen. Ich glaube sogar, dass dieser Algorithmus anhand eines illustrierten Beispiels viel mehr Sinn ergibt. Da es sich bei Heaps um eine Art Baum handelt, ist es hilfreich, sie zu visualisieren, so wie wir es bei Binärbäumen tun. Also machen wir das jetzt gleich!
Hast du schon einmal unter die Haube von Heap Sort geschaut?
Ja, es ist Zeit für meinen absoluten Lieblingsteil beim Lernen von Heap Sort: das Zeichnen! Hurra! Um zu verstehen, was unter der Haube von Heap-Sort vor sich geht, werden wir mit einem kleinen, unsortierten Datensatz arbeiten.
Wir beginnen mit einem unsortierten Array mit fünf Elementen, die völlig durcheinander sind: .
Da wir mit Heap-Sortierung arbeiten, müssen wir dieses Array zunächst in einen Heap umwandeln.
In der hier gezeigten Abbildung können Sie sehen, dass das Array in einen Baum umgewandelt wurde – es ist noch kein Heap, weil es noch nicht in einer maximalen oder minimalen Heap-Reihenfolge ist! Wir können sehen, dass dies der Fall ist, weil 3 weder das größte noch das kleinste Element ist, und dennoch ist es im Moment der Wurzelknoten. Dies ist einfach ein Baum, wobei die Elemente aus dem Array direkt in ein binäres Baumformat übersetzt werden.
Da wir aber mit einem Max Heap arbeiten müssen, müssen wir unsere Struktur von einem binären Baum in einen Max Heap umwandeln. Beachten Sie, dass im Max Heap die Elternknoten alle größer sind als ihre Kinder. Letzte Woche haben wir die Algorithmen kennen gelernt, die es uns ermöglichen, die Kindknoten aus dem Index eines Arrays zu bestimmen; diese Woche sehen wir sie in Aktion. Diese Algorithmen verwenden wir, um dieses Array in einen Baum und dann in einen Heap zu verwandeln.
Okay, jetzt haben wir einen echten Max Heap. Super! Jetzt geht es an die eigentliche Arbeit des Sortierens.
Da wir wissen, dass sich das größte Element im Wurzelknoten befindet, wissen wir auch, dass wir es ganz ans Ende des Arrays setzen müssen, an den letzten verfügbaren Indexpunkt. Wir tauschen also den Wurzelknoten mit dem letzten Knoten aus. Sobald wir diesen Tausch vorgenommen haben, enthält unser letzter Knoten das größte Element mit dem höchsten Wert.
Cool! Jetzt können wir sehen, dass 19, das größte Element, das früher der Wurzelknoten war, jetzt an der letzten Position im Array steht. Und da es relativ zum Rest der Elemente „sortiert“ ist, können wir es vollständig aus dem Heap entfernen.
Die gute Nachricht ist, dass wir jetzt einen Knoten weniger in unserem Heap haben, den wir sortieren müssen! Die schlechte Nachricht? Unser Heap ist eigentlich kein Heap mehr: Er verstößt gegen die Heap-Ordnungsregel, da er kein Max-Heap ist. Beachten Sie, dass 1 der Wurzelknoten ist, aber er ist definitiv nicht größer als seine beiden Kindknoten, 14 und 7. Wir müssen ihn also an die richtige Stelle im Baum verschieben.
Lassen Sie uns diesen Baum heapifizieren und ihn wieder zu einem max heap machen!
Gut! In der obigen Abbildung sehen wir, dass wir zuerst 1 und 14 vertauscht haben, und dann 1 und 8. Jetzt sind wir wieder bei einem richtigen Max Heap. Wir können die gleichen Schritte wiederholen, die wir beim Sortieren des Elements 19 gemacht haben:
→ Zuerst vertauschen wir den ersten und den letzten Knoten.
→ Dann heapifizieren wir den Baum, bis er wieder ein richtiger Max Heap ist.
Lassen Sie uns das mit unserem neuen Wurzelknoten tun, dem Element 14. So würden unsere nächsten beiden Schritte aussehen:
Rad! Wir haben den ersten und den letzten Knoten vertauscht und dann den letzten Knoten, 14, entfernt, da er sich an seiner sortierten Position befand. Als Nächstes mussten wir nur noch den Wurzelknoten an die richtige Stelle verschieben und das Element 3 heapifizieren, bis wir wieder einen maximalen Heap-Zustand erreicht hatten.
Wir würden dies noch drei weitere Male tun. Schließlich bliebe nur noch 1 übrig, der letzte Knoten im Heap. An diesem Punkt wäre der Heap-Sortieralgorithmus beendet, und wir wüssten, dass 1 das erste Element im Array wäre, und wir wüssten, dass das Array endlich sortiert wäre.
Hier ist eine großartige Visualisierung des gesamten Prozesses, den wir gerade durchlaufen haben. Beachten Sie, wie bei jeder iterativen Sortierung das größte unsortierte Element an seinem richtigen Platz im Heap und dann im Array landet.
Haufensortierung: Wofür ist sie gut?
Als ich das erste Mal über Haufensortierung las, kam mir etwas an dem Algorithmus seltsam bekannt vor. Erst nachdem ich Heap-Sort veranschaulicht hatte, wurde mir klar, woher mein Déjà-vu-Gefühl kam: Heap-Sort war fast genau wie Selection-Sort! Vielleicht erinnern Sie sich noch, dass selection sort ein Sortieralgorithmus ist, der eine Liste unsortierter Elemente sortiert, indem er eine Liste von Elementen durchläuft, das kleinste Element findet und es in eine sortierte Liste verschiebt. Er sortiert weiter, indem er das kleinste unsortierte Element findet und es der sortierten Liste hinzufügt.
Hört sich das nicht sehr nach Heap-Sortierung an, nur eben umgekehrt?
Es stellt sich heraus, dass die Haufensortierung in ihrer Logik der Auswahlsortierung sehr ähnlich ist: Beide Algorithmen finden entweder das kleinste oder das größte Element, „wählen“ es aus und setzen dieses Element an die richtige Stelle in der sortierten Liste.
So ähnlich sie sich auch sind, die Haufensortierung ist in einer Hinsicht viel besser als die Auswahlsortierung: ihre Leistung! Heap-Sortierung ist im Grunde eine verbesserte Version der Auswahlsortierung. Ja, sie findet das größte Element in einer unsortierten Sammlung und ordnet es am Ende der Liste an – aber sie erledigt all diese Arbeit viel schneller, als es die Auswahlsortierung tun würde!
Okay, wie viel schneller ist die Haufensortierung also? Und warum ist sie schneller?
Werfen wir einen Blick auf den Code. Es gibt verschiedene Implementierungen von Heap-Sort, und der folgende Code ist der JavaScript-Implementierung von Heap-Sort von Rosetta Code entnommen. Sie werden sich erinnern, dass Heap Sort zwei wichtige Teile hat: buildMaxHeap und heapify. Wir können sie in der folgenden Version von heapSort in Aktion sehen.
Die Funktion buildMaxHeap erledigt die eigentliche Arbeit der Erstellung des maximalen Heaps. Beachten Sie, dass auch diese Funktion die Funktion heapify aufruft, die ein Element nach dem anderen an die richtige Stelle im Heap verschiebt.
Die Funktion heapify ist ziemlich wichtig, also sehen wir sie uns mal an. Beachten Sie, dass sie sich auf die Algorithmen verlässt, um das linke und rechte Kind eines Knotens zu bestimmen, was wir letzte Woche besprochen haben, als wir zum ersten Mal etwas über Heaps gelernt haben.
Und zu guter Letzt die Funktion swap, die wir schon in anderen Sortieralgorithmen gesehen haben, die wir uns aber kurz ansehen sollten, um uns daran zu erinnern, was sie tut:
Okay, jetzt, da wir einen gewissen Kontext dafür haben, wie diese Funktionen interagieren und sich gegenseitig aufrufen, lassen Sie uns zu unserer ursprünglichen Frage zurückkehren, wie und warum Heap Sort so viel effizienter ist als Selection Sort! Wenn wir uns den Code genauer ansehen, werden uns zwei Dinge auffallen: Erstens müssen wir den Max Heap einmal aufbauen, indem wir ihm alle Elemente des Arrays übergeben; zweitens müssen wir alle Elemente im Heap immer wieder heapifizieren, mit Ausnahme des ersten Wurzelknotenelements.
Diese beiden Beobachtungen sind eigentlich der Schlüssel zu der Frage, wie und warum heap sort so schnell ist, wie es ist. Der Aufruf von buildMaxHeap benötigt O(n)-Zeit, da jedes einzelne Element dem Heap hinzugefügt werden muss, und eine größere Anzahl von Elementen bedeutet einen größeren Heap. Bedenken Sie jedoch, dass wir es mit einem Binärbaum zu tun haben, und Binärbäume sind von Natur aus logarithmisch. Obwohl wir also heapify immer wieder aufrufen müssen, ist der Aufruf dieser Funktion eigentlich ziemlich schnell, da er in logarithmischer Zeit oder O(log n) abläuft.
Die Kombination dieser beiden Zeitkomplexe haben wir schon einmal gesehen! Heap Sort läuft in linearer Zeit, oder in Big O Notation, O(n log n). Obwohl Heap-Sortierung so ähnlich aussieht wie Selection-Sortierung, ist sie viel schneller! Selection Sort läuft in quadratischer Zeit, oder O(n²), was viel weniger effizient ist als linearithmische Zeit.
Lassen Sie uns kurz die anderen Möglichkeiten betrachten, wie Heap Sort mit anderen Sortieralgorithmen verglichen wird.
Die Haufensortierung transformiert das Array, das ihr übergeben wird, während sie sortiert; im Gegensatz zu einigen Sortieralgorithmen erstellt sie keine völlig separate Kopie der Eingabedaten. Dies macht ihn zu einem In-Place-Sortieralgorithmus. Heap Sort benötigt auch keinen externen Speicher und ist ein interner Sortieralgorithmus. Er wird iterativ ausgeführt (und ist daher nicht rekursiv) und vergleicht zwei Elemente auf einmal, wenn er sie austauscht und die heapify-Funktion aufruft, was ihn zu einem Vergleichssortieralgorithmus macht.
Aufgrund der Natur von Heaps und der heapify-Funktion können wir uns jedoch nicht darauf verlassen, dass Elemente ihre Reihenfolge beibehalten, wenn es doppelte Elemente gibt! Heap-Sort ist also instabil; dies ist ein Hauptunterschied zwischen Merge-Sort und Heap-Sort, die beide auf Baumstrukturen angewiesen sind, um so effizient zu arbeiten. Merge-Sort gewinnt jedoch den Kampf um die Stabilität, während Heap-Sort in dieser Kategorie versagt.
Trotz ihrer Unterschiede sind sich Merge-Sort und Heap-Sort in einem Punkt einig: Ohne binäre Bäume wären beide verloren!
Ressourcen
Es gibt einige wirklich fantastische Kursnotizen und Vorlesungen über Heap-Sortierung sowie einige gute Video-Tutorials. Ich habe ein wenig gegoogelt, damit Sie das nicht tun müssen!
- Einführung in Algorithmen: Heap Sort, MIT
- Algorithmen: Heap Sort, Professor Ching-Chi Lin
- Heap sort, Growing with the Web
- Heap sort in 4 minutes, Michael Sambol
- Heap sort: Max heap, strohtennis
Leave a Reply