Heap Sort Algorithmus (Mit Code in Python und C++)
Sarah Chen
Was ist ein Heap-Sortieralgorithmus?
Heapsort ist einer der beliebtesten und schnellsten Sortieralgorithmen. Er basiert auf der vollständigen binären Baumdatenstruktur. Wir suchen nach dem maximalen Element und platzieren es ganz oben für den maximalen Heap. Wir platzieren es auf dem übergeordneten Knoten des binären Baums.
Nehmen wir an, ein Array sei gegeben, Daten = [10,5, 7, 9, 4, 11, 45, 17, 60].
Wenn im Array der i-te Index (i=0,1,2,3 …) ein übergeordneter Knoten ist, sind (2i+1) und (2i+2) die linken und rechten untergeordneten Knoten. Das Erstellen eines vollständigen Binärbaums mit diesem Array sieht folgendermaßen aus:
Wir führen den Heapify-Prozess vom Anfang bis zum Ende des Arrays durch. Wenn wir das Array zunächst in einen Baum umwandeln, sieht es wie oben aus. Wir können sehen, dass es keine Heap-Eigenschaft (Min-Heap oder Max-Heap) beibehält. Wir erhalten das sortierte Array, indem wir den Heapify-Prozess für alle Knoten durchführen.
Anwendung der Heap-Sortierung
Hier ist eine Verwendung des Heap-Sortieralgorithmus:
- Der Aufbau von „Prioritätswarteschlangen“ erfordert eine Heap-Sortierung. Weil Heapsort das Element nach jedem Einfügen sortiert hält.
- Die Heap-Datenstruktur ist effizient beim Finden des kth größtes Element in einem bestimmten Array.
- Der Linux-Kernel verwendet standardmäßig die Heap-Sortierung Sortieralgorithmus da es eine Speicherkomplexität von O (1) hat.
Erstellen Sie eine Heap-Sortierung anhand eines Beispiels
Hier werden wir einen maximalen Heap aus dem folgenden vollständigen Binärbaum konstruieren.
Die Blattknoten sind 17, 60, 4, 11 und 45. Sie haben keine untergeordneten Knoten. Deshalb sind sie Blattknoten. Daher starten wir die Heapify-Methode von ihrem übergeordneten Knoten aus. Hier sind die Schritte:
Schritt 1) Wählen Sie den Unterbaum ganz links aus. Wenn die untergeordneten Knoten größer sind, tauschen Sie den übergeordneten Knoten mit dem untergeordneten Knoten aus.
Hier ist der übergeordnete Knoten 9. Und die untergeordneten Knoten sind 17 und 60. Da 60 der größte ist, werden 60 und 9 vertauscht, um die beizubehalten max Haufen.
Schritt 2) Jetzt wird der am weitesten links stehende Teilbaum gehäuft. Der nächste übergeordnete Knoten ist 7. Dieser übergeordnete Knoten hat zwei untergeordnete Knoten, und der größte ist 45. Daher werden 45 und 7 vertauscht.
Schritt 3) Die Knoten 60 und 4 haben den übergeordneten Knoten 5. Da „5“ kleiner als der untergeordnete Knoten 60 ist, wird er vertauscht.
Schritt 4) Jetzt hat Knoten 5 den untergeordneten Knoten 17,9. Dadurch wird die Max-Heap-Eigenschaft nicht beibehalten. Also wird 5 durch 17 ersetzt.
Schritt 5) Knoten 10 wird mit 60 und dann mit 17 ausgetauscht. Der Vorgang sieht wie folgt aus.
Schritt 6) Bis Schritt 5 haben wir den maximalen Heap erstellt. Jeder übergeordnete Knoten ist größer als seine untergeordneten Knoten. Der Wurzelknoten hat den Maximalwert (60).
Hinweis: Um das sortierte Array zu erstellen, müssen wir den Knoten mit dem höchsten Wert durch seinen Nachfolger ersetzen.
Dieser Vorgang heißt „extrahieren max“. Da 60 der maximale Knoten ist, legen wir seine Position auf den 0. Index fest und erstellen den Heap ohne Knoten 60.
Schritt 7) Wenn 60 entfernt wird, ist der nächste Maximalwert 45. Wir werden den Prozess „Max extrahieren“ erneut von Knoten 45 ausführen.
Diesmal erhalten wir 45 und ersetzen den Wurzelknoten durch seinen Nachfolger 17.
Wir müssen Leistung erbringen“Extrahieren Sie max” bis alle Elemente sortiert sind.
Nachdem wir diese Schritte ausgeführt haben, bis wir alle Maximalwerte extrahiert haben, erhalten wir das folgende Array.
Was ist ein binärer Heap?
Ein binärer Heap ist eine Art vollständiger binärer Baum Datenstruktur. In einer solchen Baumstruktur ist der übergeordnete Knoten entweder größer oder kleiner als die untergeordneten Knoten. Wenn der übergeordnete Knoten kleiner ist, wird der Heap „Min Heap“ genannt, und wenn der übergeordnete Knoten größer ist, wird der Heap „Max Heap“ genannt.
Hier sind Beispiele für Min Heap und Max Heap.
Wenn Sie in der obigen Abbildung den „Min Heap“ bemerken, ist der übergeordnete Knoten immer kleiner als seine untergeordneten Knoten. An der Spitze des Baumes finden wir den kleinsten Wert 10.
Ebenso ist beim „Max Heap“ der übergeordnete Knoten immer größer als die untergeordneten Knoten. Das maximale Element ist am Kopfknoten für den „Max Heap“ vorhanden.
Was ist „Heapify“?
„Heapify“ ist das Prinzip des Heaps, das die Position des Knotens sicherstellt. Bei Heapify behält ein Max-Heap immer eine Beziehung zwischen übergeordnetem und untergeordnetem Knoten bei, d. h. der übergeordnete Knoten ist größer als die untergeordneten Knoten.
Wenn beispielsweise ein neuer Knoten hinzugefügt wird, müssen wir den Heap neu gestalten. Möglicherweise müssen wir jedoch die Knoten ändern oder austauschen oder das Array neu anordnen. Dieser Vorgang der Umgestaltung eines Heaps wird als „Heapify“ bezeichnet.
Hier ist ein Beispiel, wie Heapify funktioniert:
Hier sind die Schritte für Heapify:
Schritt 1) Knoten 65 als rechtes untergeordnetes Element von Knoten 60 hinzugefügt.
Schritt 2) Überprüfen Sie, ob der neu hinzugefügte Knoten größer als der übergeordnete Knoten ist.
Schritt 3) Da er größer als der übergeordnete Knoten ist, haben wir den rechten untergeordneten Knoten mit seinem übergeordneten Knoten vertauscht.
So erstellen Sie den Heap
Bevor wir den Heap erstellen oder einen Baum heapifizieren, müssen wir wissen, wie wir ihn speichern werden. Da der Heap ein vollständiger binärer Baum ist, ist es besser, einen Array um die Daten des Heaps zu speichern.
Nehmen wir an, ein Array enthält insgesamt n Elemente. Wenn der „i“-te Index ein übergeordneter Knoten ist, befindet sich der linke Knoten am Index (2i+1), und der rechte Knoten befindet sich am Index (2i+2). Wir gehen davon aus, dass der Array-Index bei 0 beginnt.
Lassen Sie uns damit einen maximalen Heap in einem Array wie folgt speichern:
Der Heapify-Algorithmus behält die Heap-Eigenschaft bei. Wenn der übergeordnete Knoten nicht den Extremwert (kleiner oder größer) hat, wird er mit dem extremsten untergeordneten Knoten ausgetauscht.
So heben Sie einen maximalen Heap auf:
Schritt 1) Beginnen Sie am Blattknoten.
Schritt 2) Finden Sie das Maximum zwischen Eltern und Kindern.
Schritt 3) Tauschen Sie die Knoten aus, wenn der untergeordnete Knoten einen größeren Wert hat als der übergeordnete.
Schritt 4) Gehen Sie eine Ebene höher.
Schritt 5) Befolgen Sie die Schritte 2,3,4, bis wir den Index 0 erreichen, oder sortieren Sie den gesamten Baum.
Hier ist der Pseudocode für rekursives Heapify (max heap):
def heapify(): input→ array, size, i largest = i left = 2*i + 1 right = 2*i + 2 if left<n and array[largest ] < array[left]: largest = left if right<n and array[largest ] < array[right]: largest = right If largest not equals i: swap(array[i],array[largest]) heapify(array,n,largest)
Pseudocode für Heap-Sortierung
Hier ist der Pseudocode für den Heap-Sortieralgorithmus:
Heapify(numbers as an array, n as integer, i as integer): largest = i left = 2i+1 right= 2i+2 if(left<=n) and (numbers[i]<numbers[left]) largest=left if(right<=n) and (numbers[i]<numbers[right]) largest=right if(largest != i) swap(numbers[i], numbers[largest]) Heapify(numbers,n,largest) HeapSort(numbers as an array): n= numbers.size() for i in range n/2 to 1 Heapify(numbers,n,i) for i in range n to 2 Swap numbers[i] with numbers[1] Heapify(numbers,i,0)
Beispiel für Heap Sort Code in C++
#include <iostream>
using namespace std;
void display(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << "\t";
}
cout << endl;
}
void heapify(int numbers[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && numbers[left] < numbers[largest])
{
largest = left;
}
if (right < n && numbers[right] < numbers[largest])
{
largest = right;
}
if (largest != i)
{
//uncomment the following line to see details in output
//cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
swap(numbers[i], numbers[largest]);
heapify(numbers, n, largest);
}
}
void heapSort(int numbers[], int n)
{
for (int i = n/2 - 1; i >= 0; i--)
{
heapify(numbers, n, i);
//uncomment the following line to see details in output
//cout<<"Heapify:\t";
//display(numbers,n);
}
for (int i = n - 1; i >= 0; i--)
{
swap(numbers[0], numbers[i]);
heapify(numbers, i, 0);
}
}
int main()
{
int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
int size = sizeof(numbers) / sizeof(numbers[0]);
cout<<"Initial Array:\t";
display(numbers,size);
heapSort(numbers, size);
cout<<"Sorted Array (descending order):\t";
display(numbers, size);
}
Ausgang:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
Beispiel für Heap Sort Code in Python
def display(arr):
for i in range(len(arr)):
print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
largest = left
if right < n and numbers[right] < numbers[largest]:
largest = right
if largest != i:
numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
for i in range(n //2,-1,-1):
heapify(items, n, i) for i in range(n - 1, -1, -1):
items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)
Ausgang:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Zeitliche und räumliche Komplexitätsanalyse von Heap Sort
Es gibt Zeitkomplexität und Raumkomplexität, die wir für die Heapsortierung analysieren können. Für die Zeitkomplexität gibt es die folgenden Fälle:
- besten Case
- Durchschnittlicher Fall
- Schlimmsten Fall
Der Heap wird auf einem vollständigen Binärbaum implementiert. Auf der untersten Ebene des Binärbaums befindet sich also die maximale Anzahl an Knoten. Wenn die unterste Ebene n Knoten hat, dann hat die obere Ebene n/2 Knoten.
In diesem Beispiel verfügt Ebene 3 über vier Elemente, Ebene 2 über zwei Elemente und Ebene 1 über ein Element. Wenn insgesamt n Elemente vorhanden sind, wird die Höhe bzw. das Gesamtniveau angegeben Log2(N). Das Einfügen eines einzelnen Elements könnte also maximal Log(n)-Iterationen erfordern.
Wenn wir den maximalen Wert aus dem Heap nehmen wollen, nehmen wir einfach den Stammknoten. Dann führen wir erneut das Heapify aus. Jedes Heapify nimmt Log2(n) Zeit. Das Extrahieren des Maximums dauert O(1) Zeit.
Bester Fall der Zeitkomplexität für den Heapsort-Algorithmus
Wenn alle Elemente bereits im Array sortiert sind, dauert der Aufbau des Heaps O(n) Zeit. Denn wenn die Liste sortiert ist, dauert das Einfügen eines Elements die konstante Zeit O(1).
Daher wird es im besten Fall O(n) Zeit dauern, einen Max-Heap oder Min-Heap zu erstellen.
Durchschnittliche Fallzeitkomplexität für den Heapsort-Algorithmus
Das Einfügen eines Elements oder das Extrahieren eines Maximums dauert O(log(n)). Die durchschnittliche Zeitkomplexität für den Heapsort-Algorithmus beträgt also O(n log(n)).
Worst-Case-Zeitkomplexität für den Heapsort-Algorithmus
Ähnlich wie im durchschnittlichen Fall müssen wir im schlimmsten Fall Heapify n-mal durchführen. Jedes Heapify kostet O(log(n)) Zeit. Die Zeitkomplexität im schlimmsten Fall beträgt also O(n log(n)).
Speicherkomplexität für den Heapsort-Algorithmus
Heapsort ist ein direkt entwickelter Algorithmus. Das bedeutet, dass kein zusätzlicher oder temporärer Speicher benötigt wird, um die Aufgabe auszuführen. Wenn wir uns die Implementierung ansehen, werden wir feststellen, dass wir swap() verwendet haben, um den Austausch der Knoten durchzuführen. Es wurde keine andere Liste oder kein anderes Array benötigt. Die Speicherkomplexität beträgt also O(1).
