Heap-Sortieralgorithmus (mit Code in Python und C++)

Was ist ein Heap-Sortieralgorithmus?

Heap Sort ist einer der beliebtesten und schnelleren Sortieralgorithmen. Es basiert auf der vollständigen Binärbaum-Datenstruktur. Wir suchen nach dem maximalen Element und legen es oben für den maximalen Heap ab. Wir werden es auf dem übergeordneten Knoten des Binärbaums platzieren.

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:

Heap-Sortieralgorithmus

Wir werden das machenapify Prozess vom Anfang bis zum Ende des Arrays. Wenn wir das Array zunächst in einen Baum konvertieren, sieht es wie oben aus. Wir können sehen, dass keine Heap-Eigenschaft (Min-Heap oder Max-Heap) beibehalten wird. Wir erhalten das sortierte Array, indem wir den Befehl he ausführenapify Prozess für alle Knoten.

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 O (1) Raum com hatplexkeit.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Hier werden wir aus Folgendem einen maximalen Heap erstellenwing vollständiger Binärbaum.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Die Blattknoten sind 17, 60, 4, 11 und 45. Sie haben keine untergeordneten Knoten. Deshalb sind sie Blattknoten. Also beginnen wir mit dem Heapify Methode von ihrem übergeordneten Knoten. 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.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

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.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Schritt 3) Die Knoten 60 und 4 haben den übergeordneten Knoten 5. Da „5“ kleiner als der untergeordnete Knoten 60 ist, wird er vertauscht.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

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.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Schritt 5) Knoten 10 wird mit 60 und dann mit 17 ausgetauscht. Der Vorgang sieht wie folgt auswing.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

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.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

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 Folgendeswing Array.

Erstellen Sie eine Heap-Sortierung anhand eines Beispiels

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.

Min. Heap und Max. Heap
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 erapify"?

"Erapify„ist das Prinzip des Heaps, das die Position des Knotens sicherstellt. In Erapify, ein maximaler Heap behält immer eine Beziehung zwischen übergeordnetem und untergeordnetem Knoten bei, und das bedeutet, dass der übergeordnete Knoten größer als die untergeordneten Knoten ist.

Wenn beispielsweise ein neuer Knoten hinzugefügt wird, müssen wir den Heap umformen. Möglicherweise müssen wir jedoch die Knoten ändern oder austauschen oder das Array neu anordnen. Dieser Vorgang der Umformung eines Haufens wird „er“ genanntapify".

Hier ist ein Beispiel dafür, wie erapify funktioniert:

Hinzufügen eines neuen Knotens und Heapify
Einen neuen Knoten hinzufügen und erapify

Hier sind die Schritte für ihnapify:

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

Vor dem Bau des Haufens oder erapify Wenn wir einen Baum haben, müssen wir wissen, wie wir ihn lagern. Da der Heap ein vollständiger Binärbaum ist, ist es besser, einen zu verwenden 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.

Auf diese Weise speichern wir einen maximalen Heap in einem Array-ähnlichen Following:

Array-basierte Darstellung des Max Heap
Arraybasierte Darstellung des maximalen Heaps

Das erapify Der Algorithmus behält die Heap-Eigenschaft bei. Wenn der übergeordnete Knoten nicht über den Extremwert (kleiner oder größer) verfügt, wird er mit dem extremsten untergeordneten Knoten ausgetauscht.

Hier sind die Schritte zu ihmapify ein maximaler Heap:

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 (maximaler 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-Sortiercode 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 einen Heap-Sortiercode 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

Zeit und Raum Complexity-Analyse von Heap Sort

Es gibt Time complexity and Space complexität, die wir für die Heap-Sortierung analysieren können. Für Zeit complexity, wir haben das Following Fälle:

  1. I'm besten fall
  2. Durchschnittlicher Fall
  3. 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.

Zeit und Raum Complexity-Analyse

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 Maximalwert aus dem Heap entnehmen wollen, nehmen wir einfach den Wurzelknoten. Führen Sie dann erneut den Befehl „he“ ausapify. Jeder erapify nimmt Log2(n) Zeit. Das Extrahieren des Maximums dauert O(1) Zeit.

Best Case Time ComplexFunktionalität für den Heap-Sortieralgorithmus

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 Fallzeit ComplexFunktionalität für den Heap-Sortieralgorithmus

Das Einfügen eines Elements oder das Extrahieren eines Maximums kostet O(log(n)) Zeit. Also, die durchschnittliche Fallzeit complexity für den Heap-Sortieralgorithmus ist O(n log(n)).

Worst Case Time ComplexFunktionalität für den Heap-Sortieralgorithmus

Ähnlich wie im Durchschnittsfall könnten wir im schlimmsten Fall ihn ausführenapify n mal. Jeder erapify kostet O(log(n)) Zeit. Also, der schlimmste Fall, Zeit complexität wird sein O(n log(n)).

WeltraumkomplexFunktionalität für den Heap-Sortieralgorithmus

Heap-Sortierung ist ein direkt entwickelter Algorithmus. Das bedeutet, dass für die Ausführung der Aufgabe kein zusätzlicher oder temporärer Speicher erforderlich ist. Wenn wir uns die Implementierung ansehen, werden wir feststellen, dass wir swap() verwendet haben, um den Austausch der Knoten durchzuführen. Es war keine andere Liste oder ein anderes Array erforderlich. Also, die Weltraumkommunikationplexität ist O(1).