Ein Heap wird als „teilweise geordnet“ und nicht als „teilweise sortiert“ bezeichnet. Das Wort 'Sortieren' bedeutet vollständiges Ordnen (vollständige Sortierung). Ein Heap ist teilweise nicht willkürlich geordnet. Ein Heap ist teilweise nach einem Kriterium (Muster) geordnet, wie unten gezeigt.
Heapsort besteht also aus zwei Phasen: Erstellen des Heaps und Extrahieren des geordneten Elements von der Spitze des Heaps. In der zweiten Stufe wird nach jeder Extraktion der Haufen neu aufgebaut. Jeder Wiederaufbau ist schneller als der ursprüngliche Bauprozess, da der Wiederaufbau von einem vorherigen Bau aus erfolgt, bei dem ein Element entfernt wurde. Und damit sortiert heapsort eine komplett unsortierte Liste.
Das Ziel dieses Artikels ist es, Heapsort kurz zu erklären und dann seine Zeitkomplexität zu erzeugen (siehe die Bedeutung von Zeitkomplexität unten). Gegen Ende wird in C++ codiert.
Minimaler Heap
Ein Heap kann ein Minimum-Heap oder ein Maximum-Heap sein. Ein Max-Heap ist einer, bei dem das erste Element das höchste Element ist und der gesamte Baum oder die entsprechende Liste teilweise in absteigender Reihenfolge geordnet ist. Ein Min-Heap ist einer, bei dem das erste Element das kleinste Element ist und die gesamte Liste teilweise in aufsteigender Reihenfolge geordnet ist. In diesem Artikel wird nur der minimale Heap betrachtet. Hinweis: In der Heap-Thematik wird ein Element auch als Knoten bezeichnet.
Ein Heap ist ein vollständiger binärer Baum. Der Binärbaum kann als Array (Liste) ausgedrückt werden; von oben nach unten und von links nach rechts lesen. Die Heap-Eigenschaft für einen Min-Heap ist, dass ein Elternknoten kleiner oder gleich jedem seiner beiden Kinder ist. Ein Beispiel für eine ungeordnete Liste ist:
| 9 | 19 | 24 | 5 | 3 | elf | 14 | 22 | 7 | 6 | 17 | fünfzehn | Null | Null | Null |
| 0 | 1 | zwei | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf | 12 | 13 | 14 |
Die erste Zeile dieser Tabelle sind die Elemente des Arrays. In der zweiten Zeile befinden sich die nullbasierten Indizes. Diese Liste von Elementen kann als Baum ausgedrückt werden. Die Null-Elemente wurden hinzugefügt, um einen vollständigen Binärbaum zu erstellen. Genau genommen sind die Null-Elemente nicht Teil der Liste (des Baums). Diese Liste hat keine Reihenfolge, also ist sie noch kein Heap. Es wird zu einem Heap, wenn es gemäß der Heap-Eigenschaft eine teilweise Ordnung hatte.
Beziehung zwischen Knoten und Indizes
Denken Sie daran, dass ein Heap ein vollständiger Binärbaum ist, bevor Sie die Heap-Konfiguration (Heap-Eigenschaft) haben. Die vorherige Liste ist noch kein Heap, da die Elemente der Heap-Eigenschaft nicht gehorchen. Es wird zu einem Heap, nachdem Elemente gemäß der Min-Heap-Eigenschaft in Teilreihenfolge neu angeordnet wurden. Partielle Ordnung kann als partielle Sortierung angesehen werden (obwohl das Wort „sortieren“ vollständige Ordnung bedeutet).
Unabhängig davon, ob ein Binärbaum ein Haufen ist oder nicht, hat jeder Elternteil zwei Kinder, mit Ausnahme der (letzten) Blattknoten. Es gibt eine mathematische Beziehung zwischen den Indizes zwischen jedem Elternteil und seinen Kindern. Es ist wie folgt: Wenn der Elternteil am Index i ist, dann ist das linke Kind am Index:
zwei * ich + 1und das rechte Kind ist am Index:
zwei * ich + zweiDies ist für die nullbasierte Indizierung. Also hat ein Elternteil bei Index 0 sein linkes Kind bei Index 2×0+1=1 und sein rechtes Kind bei 2×0+2=2. Ein Elternteil bei Index 1 hat sein linkes Kind bei Index 2×1+1=3 und sein rechtes Kind bei Index 2×1+2=4; usw.
Durch die Min-Heap-Eigenschaft ist ein Elternteil bei i kleiner oder gleich dem linken Kind bei 2i+1 und kleiner oder gleich dem rechten Kind bei 2i+2.
Haufen
Heapifying bedeutet, einen Haufen zu bauen. Es bedeutet, die Elemente einer Liste (oder eines entsprechenden Baums) so neu anzuordnen, dass sie die Heap-Eigenschaft erfüllen. Am Ende des Haufenbildungsprozesses ist die Liste oder der Baum ein Haufen.
Wenn die vorherige unsortierte Liste gehäuft wird, wird sie zu:
| 3 | 5 | elf | 7 | 6 | fünfzehn | 14 | 22 | 9 | 19 | 17 | 24 | Null | Null | Null |
| 0 | 1 | zwei | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf | 12 | 13 | 14 |
Hinweis: Es gibt 12 Elemente und nicht 15 in der Liste. In der zweiten Zeile befinden sich die Indizes. Beim Haldenbau mussten Elemente überprüft und teilweise ausgetauscht werden.
Beachten Sie, dass das kleinste und erste Element 3 ist. Die restlichen Elemente folgen aufsteigend, aber wellenförmig. Wenn die linken und rechten Kinder an den Positionen 2i+1 und 2i+2 jeweils größer oder gleich dem Elternteil an i sind, dann ist dies ein Min-Heap. Dies ist keine vollständige Bestellung oder Sortierung. Dies ist gemäß der Heap-Eigenschaft eine teilweise Ordnung. Von hier aus beginnt die nächste Stufe für die Heap-Sortierung.
Zeitkomplexität häufen
Die Zeitkomplexität ist die relative Laufzeit eines Codes. Es kann als die Anzahl der Hauptoperationen angesehen werden, die dieser Code ausführen muss. Es gibt verschiedene Algorithmen für die Heap-Bildung. Die effizientesten und schnellsten teilen die Liste kontinuierlich durch zwei, prüfen die Elemente von unten und tauschen dann einige Elemente aus. Sei N die Anzahl praktischer Elemente in der Liste. Bei diesem Algorithmus ist die maximale Anzahl der Hauptoperationen (Austauschen) N. Die Zeitkomplexität für das Heapifizieren wurde früher angegeben als:
Ö ( n )Wobei n N ist und die maximal mögliche Anzahl von Hauptoperationen ist. Diese Notation wird Big-O-Notation genannt. Es beginnt mit O in Großbuchstaben, gefolgt von Klammern. Innerhalb der Klammern steht der Ausdruck für die maximal mögliche Anzahl von Operationen.
Denken Sie daran: Die Addition kann zu einer Multiplikation werden, wenn sich das Gleiche, das hinzugefügt wird, wiederholt.
Heapsort-Illustration
Die vorherige unsortierte Liste wird verwendet, um Heapsort zu veranschaulichen. Die angegebene Liste ist:
9 19 24 5 3 elf 14 22 7 6 17 fünfzehnDer aus der Liste erzeugte Min-Heap ist:
3 5 elf 7 6 fünfzehn 14 22 9 19 17 24Die erste Stufe von Heapsort besteht darin, den produzierten Heap zu produzieren. Dies ist eine teilweise geordnete Liste. Es ist keine sortierte (vollständig sortierte) Liste.
Die zweite Stufe besteht aus dem Entfernen des kleinsten Elements, das das erste Element ist, aus dem Haufen, dem erneuten Aufhäufen des verbleibenden Haufens und dem Entfernen der kleinsten Elemente in den Ergebnissen. Das kleinste Element ist immer das erste Element im neu gehäuften Haufen. Die Elemente werden nicht entfernt und weggeworfen. Sie können in der Reihenfolge, in der sie entfernt werden, an ein anderes Array gesendet werden.
Am Ende würde das neue Array alle Elemente (vollständig) in aufsteigender Reihenfolge sortiert haben; und nicht mehr nur teilgeordnet.
In der zweiten Stufe ist das erste, was zu tun ist, 3 zu entfernen und in das neue Array zu platzieren. Die Ergebnisse sind:
3und
5 elf 7 6 fünfzehn 14 22 9 19 17 24Die restlichen Elemente müssen aufgeschüttet werden, bevor das erste Element extrahiert wird. Der Haufen der verbleibenden Elemente kann werden:
5 6 7 9 fünfzehn 14 22 elf 19 17 24Das Extrahieren von 5 und das Hinzufügen zur neuen Liste (Array) ergibt die Ergebnisse:
3 5und
6 7 9 fünfzehn 14 22 elf 19 17 24Eine Häufung des verbleibenden Satzes würde ergeben:
6 7 9 fünfzehn 14 22 elf 19 17 24Das Extrahieren von 6 und das Hinzufügen zur neuen Liste (Array) ergibt die Ergebnisse:
3 5 6und
7 9 fünfzehn 14 22 elf 19 17 24Eine Häufung des verbleibenden Satzes würde ergeben:
7 9 elf 14 22 fünfzehn 19 17 24Das Extrahieren von 7 und das Hinzufügen zur neuen Liste liefert die Ergebnisse:
3 5 6 7und
9 elf 14 22 fünfzehn 19 17 24Das Anhäufen des verbleibenden Satzes ergibt:
9 elf 14 22 fünfzehn 19 17 24Das Extrahieren von 9 und das Hinzufügen zur neuen Liste ergibt die Ergebnisse:
3 5 6 7 9und
elf 14 22 fünfzehn 19 17 24Das Anhäufen des verbleibenden Satzes ergibt:
elf 14 17 fünfzehn 19 22 24Das Extrahieren von 11 und das Hinzufügen zur neuen Liste liefert die Ergebnisse:
3 5 6 7 9 elfund
14 17 fünfzehn 19 22 24Eine Häufung des verbleibenden Satzes würde ergeben:
14 17 fünfzehn 19 22 24Das Extrahieren von 14 und das Hinzufügen zur neuen Liste ergibt die Ergebnisse:
3 5 6 7 9 elf 14und
17 fünfzehn 19 22 24Eine Häufung des verbleibenden Satzes würde ergeben:
fünfzehn 17 19 22 24Das Extrahieren von 15 und das Hinzufügen zur neuen Liste ergibt die Ergebnisse:
3 5 6 7 9 elf 14 fünfzehnund
17 19 22 24Eine Häufung des verbleibenden Satzes würde ergeben:
17 19 22 24Das Extrahieren von 17 und das Hinzufügen zur neuen Liste ergibt die Ergebnisse:
3 5 6 7 9 elf 14 fünfzehn 17und
19 22 24Eine Häufung des verbleibenden Satzes würde ergeben:
19 22 24Das Extrahieren von 19 und das Hinzufügen zur neuen Liste liefert die Ergebnisse:
3 5 6 7 9 elf 14 fünfzehn 17 19und
22 24Das Anhäufen des verbleibenden Satzes ergibt:
22 24Das Extrahieren von 22 und das Hinzufügen zur neuen Liste ergibt die Ergebnisse:
3 5 6 7 9 elf 14 fünfzehn 17 19 22und
24Das Anhäufen des verbleibenden Satzes ergibt:
24Das Extrahieren von 24 und das Hinzufügen zur neuen Liste liefert die Ergebnisse:
3 5 6 7 9 elf 14 fünfzehn 17 19 22 24und
- - -Das Heap-Array ist jetzt leer. Alle Elemente, die es am Anfang hatte, sind jetzt im neuen Array (Liste) und sortiert.
Heapsort-Algorithmus
Obwohl der Leser vielleicht in Lehrbüchern gelesen hat, dass Heapsort aus zwei Stufen besteht, kann Heapsort immer noch als aus einer Stufe bestehend angesehen werden, die das gegebene Array iterativ verkleinert. Damit lautet der Algorithmus zum Sortieren mit Heapsort wie folgt:
- Heapifizieren Sie die unsortierte Liste.
- Extrahieren Sie das erste Element des Haufens und fügen Sie es als erstes Element der neuen Liste ein.
- Heapifizieren Sie die verbleibende Liste.
- Extrahieren Sie das erste Element des neuen Haufens und fügen Sie es als nächstes Element in die neue Liste ein.
- Wiederholen Sie die vorherigen Schritte der Reihe nach, bis die Heap-Liste leer ist. Am Ende ist die neue Liste sortiert.
Heapsort Time Complexity Proper
Der einstufige Ansatz wird verwendet, um die Zeitkomplexität für Heapsort zu bestimmen. Angenommen, es sind 8 unsortierte Elemente zu sortieren.
Die mögliche maximale Anzahl von Operationen zum Heapifizieren der 8 Elemente ist 8 .Das mögliche maximale Anzahl von Operationen, um die verbleibenden zu häufen 7 Elemente ist 7 .
Das mögliche maximale Anzahl von Operationen, um die verbleibenden zu häufen 6 Elemente ist 6 .
Das mögliche maximale Anzahl von Operationen, um die verbleibenden zu häufen 5 Elemente ist 5 .
Das mögliche maximale Anzahl von Operationen, um die verbleibenden zu häufen 4 Elemente ist 4 .
Das mögliche maximale Anzahl von Operationen, um die verbleibenden zu häufen 3 Elemente ist 3 .
Das mögliche maximale Anzahl von Operationen, um die verbleibenden zu häufen zwei Elemente ist zwei .
Das mögliche maximale Anzahl von Operationen, um die verbleibenden zu häufen 1 Element ist 1 .
Die mögliche maximale Anzahl von Operationen beträgt:
8 + 7 + 6 + 5 + 4 + 3 + zwei + 1 = 36Der Durchschnitt dieser Anzahl von Operationen ist:
36 / 8 = 4.5Beachten Sie, dass sich die letzten vier Haufen in der vorherigen Abbildung nicht geändert haben, als das erste Element entfernt wurde. Einige der vorherigen Haufen haben sich auch nicht geändert, als das erste Element entfernt wurde. Damit ist eine bessere durchschnittliche Anzahl von Hauptoperationen (Swappings) 3 und nicht 4,5. Eine bessere durchschnittliche Gesamtzahl der Hauptoperationen ist also:
24 = 8 x 3=> 24 = 8 x Protokoll < sub > zwei < / sub > 8
seit log zwei 8 = 3.
Im Allgemeinen beträgt die durchschnittliche Fallzeitkomplexität für Heapsort:
Ö ( n. log2n )Wobei der Punkt Multiplikation bedeutet und n N ist, die Gesamtzahl der Elemente in der Liste (jede Liste).
Beachten Sie, dass die Operation zum Extrahieren des ersten Elements ignoriert wurde. Beim Thema Zeitkomplexität werden Operationen, die relativ kurze Zeiten in Anspruch nehmen, ignoriert.
Codierung in C++
In der Algorithmenbibliothek von C++ gibt es eine Funktion make_heap(). Die Syntax lautet:
Schablone < Klasse RandomAccessIterator, Klasse Vergleichen >constexpr Leere make_haufen ( RandomAccessIterator zuerst, RandomAccessIterator zuletzt, Comp vergleichen ) ;
Es nimmt den Iterator, der auf das erste Element eines Vektors zeigt, als erstes Argument und dann den Iterator, der direkt hinter das Ende des Vektors zeigt, als letztes Argument. Für die vorherige unsortierte Liste würde die Syntax wie folgt verwendet werden, um einen minimalen Heap zu erhalten:
Vektor < int > vtr = { 9 , 19 , 24 , 5 , 3 , elf , 14 , 22 , 7 , 6 , 17 , fünfzehn } ;Vektor < int > :: Iterator iterB = vtr. Start ( ) ;
Vektor < int > :: Iterator iterE = vtr. Ende ( ) ;
make_haufen ( iterB, iterE, größer < int > ( ) ) ;
Dieser Code ändert einen Vektorinhalt in eine minimale Heap-Konfiguration. In den folgenden C++-Vektoren werden statt zwei Arrays zwei Vektoren verwendet.
Um das erste Element eines Vektors zu kopieren und zurückzugeben, verwenden Sie die Vektorsyntax:
constexpr Referenz vorne ( ) ;Um das erste Element eines Vektors zu entfernen und wegzuwerfen, verwenden Sie die Vektorsyntax:
constexpr Iterator löschen ( const_iterator-Position )Um ein Element am Ende eines Vektors (nächstes Element) hinzuzufügen, verwenden Sie die Vektorsyntax:
constexpr Leere push_back ( konst T & x ) ;Der Beginn des Programms ist:
#include#include
#einschließen
verwenden Namensraum Standard ;
Der Algorithmus und die Vektorbibliotheken sind enthalten. Als nächstes kommt im Programm die Funktion heapsort(), die lautet:
Leere Haufensort ( Vektor < int > & altV, Vektor < int > & neuV ) {wenn ( altV. Größe ( ) > 0 ) {
Vektor < int > :: Iterator iterB = altV. Start ( ) ;
Vektor < int > :: Iterator iterE = altV. Ende ( ) ;
make_haufen ( iterB, iterE, größer < int > ( ) ) ;
int nächste = altV. Vorderseite ( ) ;
altV. löschen ( iterB ) ;
neuV. push_back ( nächste ) ;
Haufensort ( altV, neuV ) ;
}
}
Es ist eine rekursive Funktion. Es verwendet die Funktion make_heap() der C++-Algorithmusbibliothek. Das zweite Codesegment in der Funktionsdefinition extrahiert das erste Element aus dem alten Vektor nach dem Heap-Building und fügt es als nächstes Element für den neuen Vektor hinzu. Beachten Sie, dass in der Funktionsdefinition die Vektorparameter Referenzen sind, während die Funktion mit den Bezeichnern (Namen) aufgerufen wird.
Eine geeignete C++ Hauptfunktion dafür ist:
int hauptsächlich ( int Argc, verkohlen ** argv ){
Vektor < int > altV = { 9 , 19 , 24 , 5 , 3 , elf , 14 , 22 , 7 , 6 , 17 , fünfzehn } ;
Vektor < int > neuV ;
Haufensort ( altV, neuV ) ;
zum ( int ich = 0 ; ich < neuV. Größe ( ) ; ich ++ ) {
cout << neuV [ ich ] << ' ' ;
}
cout << Ende ;
Rückkehr 0 ;
}
Die Ausgabe ist:
3 5 6 7 9 elf 14 fünfzehn 17 19 22 24sortiert (vollständig).
Fazit
Der Artikel erörterte im Detail die Art und Funktion von Heap Sort, allgemein bekannt als Heapsort, als Sortieralgorithmus. Heapify Time Complexity, Heapsort-Darstellung und Heapsort als Algorithmus wurden behandelt und durch Beispiele unterstützt. Die durchschnittliche Zeitkomplexität für ein gut geschriebenes Heapsort-Programm ist O(nlog(n))