Die Eigenschaften des Haufens
Ein Haufen ist ein völlig binärer Baum, der in der Realität durch ein Array implementiert werden kann. Eine seiner wichtigsten Eigenschaften ist, dass jeder Knoten kleiner als (größer als) seinen untergeordneten Knoten entspricht. Der Haufen mit dem kleinsten Wurzelknoten wird als kleinster Haufen bezeichnet, und der Haufen mit dem größten Wurzelknoten wird als größter Haufen bezeichnet. Die folgende Abbildung zeigt ein Beispiel für einen größten Haufen und seine Array -Darstellung, was intuitiv erkennen kann, dass jeder Knoten größer ist als seine Kinder.
Wie in der obigen Abbildung zu sehen ist, können Knoten eines vollständig binären Baums in der Reihenfolge der Stammknotennummer 1 angeordnet werden, die dem Index in Array A entspricht (beachten Sie, dass das Index hier ab 1 beginnt). Bei einem Knoten I können wir leicht sein linkes Kind 2i erhalten, das rechte Kind ist 2i+1 und der Elternknoten I/2 ist I/2
Grundlegende Operationen von Haufen
Es gibt zwei grundlegende Operationen für den Haufen (siehe minimaler Haufen wie ein Beispiel unten):
Fügen Sie Element K ein: Fügen Sie K direkt zum Ende des Arrays hinzu und sprudeln Sie dann nach oben, um den Haufen anzupassen. Bubble Up Operation: Vergleichen Sie das Element, das an seinen übergeordneten Knoten angepasst werden soll. Wenn es größer ist als der übergeordnete Knoten, tauschen Sie es aus, bis die Eigenschaften des Haufens wiederhergestellt sind.
Extrahieren Sie den größten Wert: Der größte Wert ist das Stammelement. Löschen Sie es dann, lassen Sie das Root-Element = das letzte Blattknotenelement und sprudeln Sie dann vom Wurzelelement nach unten, um den Haufen anzupassen. Bubble Down Operation: Jedes Mal sollten Sie den kleinsten untergeordneten Knoten aus den drei Knoten auswählen, um den Knoten anzupassen, der die linken und rechten Kinder zum Austausch hat (falls der kleinste, muss er sich nicht austauschen), bis die Eigenschaften des Haufens wiederhergestellt sind.
In der Praxis ist es oft notwendig, ein ungeordnetes Array zu bauen, das N -Elemente in Haufen enthält. Der Konstruktor in der folgenden Heap -Klasse zeigt, wie ein Haufen durch _Bubbledown -Blasenanpassung erstellt wird. Der Haufen ist im Wesentlichen ein vollständig binärer Baum, und die Baumhöhe ist immer lognlogn. Der zeitaufwändige Betrieb der einzelnen Grundvorgänge besteht darin, zu sprudeln und sich anzupassen, um die Eigenschaften des Haufens zu erfüllen, sodass ihre Zeitkomplexität O (NLOGN) O (NLOGN) ist.
Java Beispiel:
// public void schwimmen (int k) {while (k/2> = 1 && weniger (pq [k/2], pq [k])) {Börse (pq, k/2, k); k = k/2; }} // Sink private void sink () {int k = 1; while (2*k <n) {int j = 2*k; if (weniger (pq [j], pq [j+1]) J ++; if (weniger (pq [k], pq [j])) börsen (pq, k, j); sonst brechen; k = j; }} Implementierungsprinzip der Heap -Sortierung
Es ist in zwei Schritte unterteilt:
1. Ordnen Sie Arrays in binärer Haufen Reihenfolge an
2. Ändern Sie die Position des Wurzelknotens und des letzten Knotens und sinken Sie dann den Wurzelknoten.
erreichen:
Vielleicht unterscheidet sich mein Code geringfügig von der obigen Animation, aber die Grundprinzipien sind ähnlich.
öffentliche Klasse Heapsort erweitert BaseSort {private int n; @Override public void sort (vergleichbar [] a) {n = A.Length-1; int k = n/2; while (k> = 1) {sink (a, k); k--; } k = 1; while (k <= n) {Börse (a, k, n-); Waschbecken (a, k); }}}