WikiDer > Heapsort

Heapsort

Die Formatierung dieses Artikels entspricht noch nicht den Wikipedia-Konventionen. Auch die Schreibweise oder Sprache kann falsch sein. Sie sind zu dieser Seite eingeladen einstellen .

Haufen sortieren ist ein Fasten Sortieralgorithmus, 1964 entwickelt von Robert W. Floyd und J. W. J. Williams. Es versucht, genau wie gerade auswahl sortieren, finde das größte Element der zu sortierenden Zeile, füge es ans Ende und fahre mit einem weniger fort, bis alles in Ordnung ist. Der Algorithmus ist sehr effizient in der Speichernutzung, ist es aber nicht stabil.

Sortieren von einem Haufen

siehe Artikel Haufen für weitere Informationen über die Heap-Datenstruktur

Die Idee hinter dem Sortieren durch Heapsort ist eigentlich ganz einfach:

Beginnen Sie mit einer Reihe von Elementen, die sortiert werden sollen.
Definieren Sie eine leere Zeile, um die Elemente in sortierter Reihenfolge zu speichern
Bilden Sie einen Max-Heap aus den zu sortierenden Elementen; wobei das Element mit dem größten Wert in der Wurzel von Baum.
Platzieren Sie dieses Element ganz hinten in der Ergebniszeile, an der hintersten noch freien Stelle. Entfernen Sie das Element aus der Reihe der zu sortierenden Elemente.
Wenn die Zeile der zu sortierenden Elemente noch nicht leer ist, fahren Sie mit Schritt 3 fort.

Um diesen Algorithmus ausführen zu können, ist es lediglich erforderlich, einen Heap aus einer Reihe von Elementen erstellen zu können.

Einen Haufen erstellen

Wie im Artikel zu lesen ist Haufen, man muss sich nicht in alle möglichen Drehungen und Wendungen winden, um einen Haufen zu bilden – ein Haufen ist im Prinzip eine Baumstruktur, kann aber trotzdem in einer Reihe gespeichert werden (wie a Array). Solange Sie sich an die Heap-Regel halten.

Die Heap-Regel lautet, dass in jedem Teilbaum des Heaps die Werte der Knoten des Teilbaums höchstens dem Wert der Wurzel des Teilbaums entsprechen. Um diese Regel beizubehalten, ist es hilfreich, sich daran zu erinnern, dass ein Blatt eines Baumes selbst ein Unterbaum ist - und da ein Blatt eines Haufens keine Kinder hat, gilt die Heap-Regel automatisch für alle Blätter des Haufens. Angenommen, wir können uns eine Möglichkeit vorstellen, die Heap-Regel für einen Unterbaum zu erhalten, bei dem der linke und der rechte Unterbaum der Wurzel Heaps sind und nur die Wurzel selbst einen zu kleinen Wert haben kann. Wenn wir einen Weg finden, dies zu tun, können wir einen Haufen aus einem beliebigen Satz von Elementen aufbauen, indem wir unten beginnen (schließlich sind die Blätter eines Haufens bereits Haufen für sich selbst) und uns nach oben arbeiten.

Nun, es gibt eine Möglichkeit, die Heap-Regel im oben beschriebenen Fall wiederherzustellen: Wir finden aus der Wurzel des Unterbaums, der Wurzel des linken Unterbaums und der Wurzel des rechten Unterbaums den größten Wert und setzen ihn in die Wurzel aus dem Baum. Da der linke und der rechte Teilbaum bereits Haufen waren, bedeutet dies, dass der höchste Wert des gesamten Teilbaums jetzt ganz oben steht. Wenn wir die Zeile mit unserem Heap-to-be darin A und den Index in dieser Zeile der Wurzel des Teilbaums i nennen, können wir das Obige wie folgt implementieren:

  MakeHeap(A: Zeile, i: Ganzzahl) = |[ links, rechts: Ganzzahl; | links, rechts := 2 * i, 2 * i 1; {siehe Artikelheap} if MAX(Ai, A.left, A.right) = A.right -> Ai, A.right := A.right, Ai [] MAX(Ai, A.left, A.right) = A.left -> Ai, A.left := A.left, Ai [] MAX(Ai, A.left, A.right) = Ai -> skip {nichts damit zu tun} fi; ]|

Das einzige Problem dabei ist, dass wir durch das Vertauschen zweier Werte den linken oder rechten Subheap durcheinander bringen können. Das Element, das wir in diesen Heap einfügen, muss die Heap-Regel für diesen freigegebenen Heap nicht beibehalten. Aber keine Sorge: Der Haufen, den wir gerade ruiniert haben, war einmal ein Haufen. Und wir haben möglicherweise nur die Wurzel vermasselt, sodass wir jetzt einen anderen Baum haben, der aus zwei Haufen mit der falschen Wurzel besteht. Und dafür hatten wir eine Lösung – wir brauchen nur MaakHeap rekursiv bewirbt sich:

  MakeHeap(A: Zeile, i: Ganzzahl) = |[ links, rechts: Ganzzahl; | links, rechts := 2 * i, 2 * i 1; {siehe Artikelheap} if MAX(A.i, A.left, A.right) = A.right -> A.i, A.right := A.right, A.i; CreateHeap(A, rechts) [] MAX(A.i, A.left, A.right) = A.left -> A.i, A.left := A.left, A.i; MakeHeap(A, left) [] MAX(A.i, A.left, A.right) = A.i -> skip {nichts damit zu tun} fi; ]|

Das ist fast gut. Das einzige, was nicht richtig ist, ist, dass wir bei der Berechnung von links und rechts manchmal Werte finden können, die nicht mehr in Zeile A (die eine endliche Betragslänge hat. A) sind:

  MakeHeap(A: Zeile, i: Ganzzahl) = |[ links, rechts: Ganzzahl; größte : ganze Zahl; | links, rechts := 2 * i, 2 * i 1; {siehe Artikelheap} if (left <= length.A) AND (A.left > Ai) -> größte := left[] (left > length.A) OR (A.left <= Ai) -> größte : = ich fi ; if (rechts <= Länge.A) AND (A.rechts > A.größte) -> größte := rechts fi ; wenn nicht (größte = i) -> A.i, A.größte := A.größte, A.i; CreateHeap(A, größte) ]|

Der erste Haufen

Das meiste Problem haben wir jetzt gelöst. Wenn wir zwei Heaps haben, können wir sie mit einem Root verbinden und die Heap-Regel wiederherstellen. Zum Beispiel können wir den Heapsort-Algorithmus ausführen, indem wir einen Heap nehmen und die Wurzel in die sortierte Zeile setzen (schließlich ist die Wurzel immer das Element mit dem höchsten Wert im Heap). Dann müssen wir entscheiden, was die neue Wurzel sein soll.

Dazu können wir natürlich eine der Wurzeln der Share Heaps wählen, die jetzt ohne gemeinsame Wurzel sind. Das ist aber schwierig, denn dann müssen wir viel bewegen, um alle Elemente wieder in die Form eines Haufens zu bekommen (man denke nur: wenn du eine Wurzel eines Teilbaums "hochziehst", dann fällt der Teilbaum auseinander – dann musst du wieder bewegen). Eine einfachere Methode besteht darin, eines der Blätter vom ehemaligen Haufen zu pflücken und an die Wurzelposition zu verschieben - ein Blatt hat keine Kinder, also können wir es nach oben verschieben, ohne viel mischen zu müssen. Natürlich ist nicht garantiert, dass wir jetzt noch einen Heap übrig haben, aber wir können diesen mit einem Aufruf von MakeHeap(A, 1) wiederherstellen. Darüber hinaus hat die Wahl einer Klinge noch einen weiteren Vorteil, auf den wir später zurückkommen werden.

Das einzige Problem, das wir jetzt haben, ist, dass wir mit einer völlig ungeordneten Zeile A beginnen. Wir müssen daraus einen ersten Heap erstellen. Natürlich haben wir MaakHeap, um uns zu helfen; aber es hilft uns mit einem einzelnen Teilbaum. Wir müssen viele Unterbäume reparieren. Es wird daher keine andere Möglichkeit geben, als MaakHeap für jedes Nicht-Blatt des Baumes aufzurufen.

Aufgrund der Art und Weise, wie der Baum in Zeile A gespeichert ist (siehe Artikel Haufen) haben alle Kinder einen höheren Index in der Warteschlange als ihre Eltern. Da ein Heap ein binärer Baum ist, ist die Anzahl der Knoten im Baum auf dieser Ebene für jede Ebene des Baums genau 1 höher als die Anzahl der Knoten in allen übergeordneten Ebenen zusammen. Das bedeutet, dass mindestens die Hälfte von A aus Blättern besteht und diese Hälfte die höchsten Indizes hat. So können wir mit dem folgenden Code einen anfänglichen Heap von unten nach oben aufbauen:

  |[n: ganze Zahl; | n := Länge.A; do i > 0 -> CreateHeap(A, n); ich := ich - 1 od ]|

Der gesamte Heapsort-Algorithmus sieht nun so aus:

  |[ var N = ...; {Länge.A = N} A : Zeile[1..N] der ganzen Zahl; {A ist unsere Anfangszeile} B : row[1..N] of integer; {B ist unsere Ergebniszeile} n : integer; MakeHeap(A : Zeile, i : Integer) = |[ var left, right : integer; größte : ganze Zahl; | links, rechts := 2 * i, 2 * i 1; {siehe Artikelheap} if (left <= N) AND (A.left > A.i) -> größte := left [] (left > N) OR (A.left <= A.i) -> größte := i fi ; if (rechts <= N) AND (A.rechts > A.größte) -> größte := rechts fi ; wenn nicht (größte = i) -> A.i, A.größte := A.größte, A.i; CreateHeap(A, größte) ]| | n := N; do i > 0 -> CreateHeap(A, n); ich := ich - 1 od; do N > 1 -> B.N, A.1 := A.1, A.(N-1); N := N-1; CreateHeap(A, 1); od; B.1 := A.1 ]|

Eine kleine Optimierung

Das oben Gesagte ist richtig, aber es macht unnötigen Gebrauch von einer zusätzlichen Zeile B. In jedem Strich des Algorithmus wird genau ein Element definitiv sortiert und fällt daher von A weg - das bedeutet, dass A immer genau so viel Platz offen hat wie dort sind sortierte Elemente. So können wir die sortierte Zeile auch gleich in A speichern.

Wir haben bereits erwähnt, dass wir beim Füllen der Wurzel nach jedem Strich ein Blatt aus dem Haufen wählen würden. Nehmen wir nun an, wir wählen immer das Blatt, das in Reihe A ZURÜCK ist. Dann fällt immer die hintere Position von A auf. Und zufälligerweise ist die Wurzel des Heaps immer der größte Wert. Wenn wir diesen Wert an die freie hinterste Stelle verschieben, erhalten wir schließlich eine perfekt sortierte Reihe A, vom kleinsten zum größten. Das sieht so aus (beachte, dass wir jetzt in MaakHeap auf die GRÖSSE von A achten müssen und nicht mehr rein auf die LÄNGE von A):

  |[ const N = ...; {Länge.A = N} var G : ganze Zahl; {size.A = G} A : Zeile[1..N] der ganzen Zahl; {A ist unsere Anfangszeile} B : row[1..N] of integer; {B ist unsere Ergebniszeile} n : integer; MakeHeap(A : Zeile, i : Integer) = |[ var left, right : integer; größte : ganze Zahl; | links, rechts := 2 * i, 2 * i 1; {siehe Artikelheap} if (left <= G) AND (A.left > A.i) -> größte := left [] (left > G) OR (A.left <= A.i) -> größte := i fi ; if (rechts <= G) AND (A.rechts > A.größte) -> größte := rechts fi ; wenn nicht (größte = i) -> A.i, A.größte := A.größte, A.i; CreateHeap(A, größte) ]| | n := N; do i > 0 -> CreateHeap(A, n); ich := ich - 1 od; G := N; do G > 0 -> A.G, A.1 := A.1, A.G; G := G - 1; CreateHeap(A, 1); od; ]|

Effizienz

Heapsort ist ein ziemlich effizienter Algorithmus, sowohl in Bezug auf die Raumnutzung als auch in Bezug auf reihenfolge der reife.

Heapsort ist ein "in-place"-Ersetzungsalgorithmus, was bedeutet, dass der Algorithmus den bereits erstellten Speicher der Sammlung wiederverwendet. In Bezug auf den Speicherplatzverbrauch ist Heapsort O(1).

Die Laufzeit wird durch die Aufrufe von MakeHeap und deren Vorlaufzeit bestimmt. Die Vorlaufzeit von MakeHeap ist linear in der Höhe des Heaps (der Länge des längsten Pfads von der Wurzel zu einem Blatt). Der Heap ist ein binärer Baum, daher ist die Höhe des Baums O(²log(N)), wodurch MaakHeap in der Komplexität logarithmisch wird. MakeHeap wird einmal im Hauptalgorithmus für jedes Element der Eingabezeile aufgerufen, wodurch die Gesamtkomplexität auf O(N*²log(N)). Beachten Sie, dass das Erstellen des anfänglichen Heaps dies nicht ändert. Auch hier ist die Hauptschleife linear und der MakeHeap ruft logarithmisch auf. Da es für jede Höhenebene im Baum eine maximale Anzahl von Knoten gibt, kann sogar festgestellt werden, dass der erste Aufbau des Heaps lineare Zeit benötigt und daher effizienter ist als der Hauptalgorithmus.

Ein Programmbeispiel

Eine Implementierung in C:

LeereHaufen sortieren(intEingang[],intLänge){intt;wenn(Länge<=1)Rückkehr;//Haufen sortierenzum(intich=1;ich<Länge;ich){// wenn i größer als sein Elternteil ist, dann tausche sie aus und prüfe dann mit seinem Großelternteil und so weiter//Elternteil von i ist (i-1)/2// Kinder von i sind i*2 1 und i*2 2zum(intja=1;Eingang[(ich-ja1)/ja]>0&&Eingang[(ich-ja1)/ja]>Eingang[(ich-2*ja1)/(2*ja)];ja*=2){t=Eingang[(ich-ja1)/ja];Eingang[(ich-ja1)/ja]=Eingang[(ich-2*ja1)/(2*ja)];Eingang[(ich-2*ja1)/(2*ja)]=t;}}// top mit letztem Element tauschen, top ist jetzt richtig, und den Rest häufent=Eingang[0];Eingang[0]=Eingang[Länge-1];Eingang[Länge-1]=t;Haufen sortieren(Eingang,Länge-1);Rückkehr;}

Alternativ – iterativ

Sortierung nach Haufen

Die Sortiermethode von Heapsort basiert auf einer Lösung von:

Erstellen Sie aus Elementen in beliebiger Reihenfolge eine Reihe dieser Elemente
Produziere diese Elemente aus dieser Reihe von Elementen in der vorgeschriebenen Reihenfolge

unter der Bedingung: Das Hinzufügen oder Entfernen eines Elements in 1 und 2 erfolgt in einer Zeit, die maximal proportional zum Logarithmus der Anzahl der Elemente in der Reihe ist.

gegeben: die vorgeschriebene Reihenfolge 'bestellt.(A,B)' ist a Gesamtbestellung und kann zwischen beliebigen Elementen in fester Zeit ausgewertet werden

Die hier vorgestellte Lösung ist eine Reihe von Elementen, die Folgendes erfüllen:

${displaystyle Heap.A=langle forall i,j:2 imes i=jvee 2 imes i 1=j:ordered.(A.i,A.j)angle }$

oder gleichwertig

${displaystyle Heap.A=langle forall i,j:i=jmathbf {div} 2:ordered.(A.i,A.j)angle }$

Erstellen eines Heaps aus Elementen in beliebiger Reihenfolge

Man fügt am Ende der Zeile, die den Heap enthält, ein neues Element hinzu und konfrontiert es mit dem Element, das dazu führen könnte, dass es die Bedingung verletzt: A.(i DIV 2) , wobei i seine aktuelle Position ist.Wenn die Heap-Bedingung nicht erfüllt ist , tauschen wir die Elemente aus. Dies wird bei jedem Strich wiederholt, wobei sich der Index mindestens halbiert, bis das neue Element die Heap-Bedingung nicht mehr stört, da keine unteren Elemente mehr vorhanden sind oder das Element den Index 0 erhält ordering ist ao reflexiv gilt geordnet(A.0,A.0) Wenn wir immer das unterste Element des Heap-Index 0 angeben, vereinfacht dies das Programm:

 { erforderlich : Heap.A[0:n) } { erforderlich : A.length > n } HeapIn ( var A : row(elem), var n : integer, in : elem, geordnet : (elem,elem)->Boolean ) |[ var i,j : ganze Zahl; { n=N UND Heap.A[0:n) } A.n:=in; i,j,n:=n DIV 2,n,n 1; do ¬geordnet.(A.i,A.j) -> A:swap(i,j); i,j:=i DIV 2,i od; { n=N 1 UND Heap.A[0:n) } ]|

Achtung. Heap.A[0:0) ist trivial gültig, sodass ein Heap elementweise mit HeapIn aus einem leeren Heap erstellt werden kann.

Elemente aus einem Heap in der vorgeschriebenen Reihenfolge produzieren

Das zu liefernde Element ist A.0, dann muss der Heap so restauriert werden, dass ein neuer A.0 entsteht und der Heap nun am Ende ein Element kürzer ist, indem man A.0 mit A.1 und . auffüllt dann der neue freie Raum Ai, der mit dem Element aus {A.(2*i),A.(2*i 1)} gefüllt werden soll, das sich zuerst für die Beförderung zu einem niedrigeren Index qualifiziert.Wir wiederholen dies, bis A(2*i 1 ) existiert nicht mehr, wobei sich der Freiraumindex pro Trick mindestens verdoppelt.Wir füllen jetzt Ai mit dem letzten Element in der Reihe, das nun potentiell ungeordnet ist bezüglich A.(i DIV 2).Dies geschieht im wie beim Hinzufügen eines neuen Elements behoben.

 { erforderlich : Heap.A[0:n) } { erforderlich : A.length >= n > 0 } HeapOut (var A : row(elem), var n : integer, var out : elem, geordnet : (elem,elem )->Boolean) |[ var i,j :integer; { n=N 1 UND Heap.A[0:n)} out:= A.0; A.0:=A.1; i,j=1,2; do j < n -> falls geordnet.(A.j,A.(j 1)) -> A.i:=A.j; i,j:=j,2*j [] geordnet.(A.(j 1),Aj) -> Ai:=A.(j 1);i,j:=j 1,2*(j 1) fi od; i,j,n:=i DIV 2,i,n-1; A.j:=A.n; do ¬geordnet.(A.i,A.j) -> A:swap(i,j); i,j:=i DIV 2,i od; { n=N UND Heap.A[0:n) } ]|

Anwendungen

Ein großer Vorteil dieses Mechanismus besteht darin, dass (fast) die Hälfte der Sortierung während der Eingabephase und der Rest während der Ausgabephase stattfindet und sich möglicherweise überlappen kann und dass der Workspace-Overhead O(1) beträgt (unabhängig von n ) macht das Verfahren attraktiv für das Sortieren von Datenmengen, die sich der Kapazität des schnelleren Direktzugriffsspeichers nähern oder diese überschreiten.

Wenn letzteres der Fall ist, kann die Routine einer externen ungeordneten Zeile maximal lange geordnete externe Unterzeilen erzeugen, die dann unter Beibehaltung der Reihenfolge zu längeren Unterzeilen zusammengeführt werden, bis der verfügbare Speicherplatz ausreicht, um alle verbleibenden Unterzeilen effizient in die gewünschte Zeile zu formen (auf dem externen Medium) zu kombinieren.

Es ist auch eine effektive 'Prioritätswarteschlange': Wenn die Aktivität mit der höchsten Priorität den frühesten Platz in der Reihenfolge erhält, kann sie in der log.n-Zeit ausgewählt werden. Eine neue Aktivität mit beliebiger Priorität kann in log.n-Zeit in die Warteschlange gestellt werden (wobei n die Anzahl der ausstehenden Aktivitäten ist).

Vor Ort sortieren

Wenn bereits eine Tabelle von Elementen im schnellen Speicher existiert und sortiert werden soll, d. h. ein in-situ-Sortierverfahren gewünscht wird, kann dies erreicht werden:

Transformieren Sie die Tabelle von 0 in Table.length in einen Heap, jedoch in umgekehrter Reihenfolge.
Platzieren Sie die aus dem Haufen erzeugten Elemente in den am Ende freigewordenen Plätzen.

falls aufsteigende Reihenfolge gewünscht:

 HeapSort (var A : row(elem)) |[ var n : integer; absteigend(elem l,elem r)->Boolean |[ l>=r ]|; { absteigend.A =  } { aufsteigend.A =  } n:=0 ; { Heap.A[0:n) } do n < A.length -> HeapIn(A,n,A.n,absteigend) od; { n = A.Länge} { Heap.A[0:n) UND aufsteigend.A[n:A.Länge) } do n > 0 -> |[var temp : elem; HeapOff(A,n,temp,absteigend); A.(n 1):=temp ]| od { Heap.A[0:0) UND aufsteigend.A[0:A.length) } ]|

Der erste Teil der Endbedingung ist keine Kunst, der zweite die Aufgabe.