Heap-Sortierung

Heap-Sort ist ein vergleichsbasierter Sortieralgorithmus. Er hat seinen Namen von der im Algorithmus verwendeten Heap-Datenstruktur. Heap ist eine binärbaumbasierte spezielle Datenstruktur. Sie hat die folgenden zwei Eigenschaften:

• Es ist ein vollständiger Binärbaum, bei dem alle Ebenen gefüllt sind, außer der letzten. Die letzte kann teilweise gefüllt sein, aber alle Knoten sind so weit links wie möglich.
• Alle Elternknoten sind kleiner/größer als ihre beiden Kinderknoten. Wenn sie kleiner sind, wird der Heap als min-heap bezeichnet, und wenn sie größer sind, wird der Heap als max-heap bezeichnet. Für einen gegebenen Index i ist der Elternknoten durch (i-1)/2 gegeben, der linke Kindknoten durch (2*i+1) und der rechte Kindknoten durch (2*i+2).

Die Heap-Sortierung funktioniert ganz ähnlich wie die Auswahlsortierung. Es wählt das maximale Element aus dem Array mit Hilfe von max-heap aus und setzt es an seine Position am Ende des Arrays. Sie verwendet eine Prozedur namens heapify(), um den Heap aufzubauen.

Heap-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.

HeapSort()

Heapify()

Beispiel für Heap-Sortierung

Angenommen, wir haben das Array: (5, 3, 4, 2, 1, 6). Wir werden es mit dem Heap-Sortieralgorithmus sortieren.

Nachdem wir den Heap aufgebaut haben, erhalten wir das Array als: (6 3 5 2 1 4).

• Erste Iteration:

• Zweite Iteration:

• Dritte Iteration:

• Vierte Iteration:

• Fünfte Iteration:

• Sechste Iteration:

Wir erhalten das sortierte Array als : (1,2,3,4,5,6)

Implementierung des Heap-Sortieralgorithmus

#include <bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
  int parent = i;
  int leftChild = 2 * i + 1;
  int rightChild = 2 * i + 2;

  if (leftChild < n && arr[leftChild] > arr[parent]) parent = leftChild;

  if (rightChild < n && arr[rightChild] > arr[parent]) parent = rightChild;

  if (parent != i) {
    swap(arr[i], arr[parent]);
    heapify(arr, n, parent);
  }
}

void heapSort(int arr[], int n) {
  for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

  for (int i = n - 1; i >= 0; i--) {
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  heapSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Komplexität des Heap-Sortieralgorithmus

Zeitkomplexität

• Durchschnittlicher Fall

Die Höhe eines vollständigen Binärbaums mit n Elementen ist maximal logn. Die Funktion heapify() kann also maximal logn Vergleiche haben, wenn ein Element von der Wurzel zum Blatt wandert. Die Funktion wird für n/2 Elemente aufgerufen, wodurch die gesamte Zeitkomplexität für die erste Stufe n/2*logn oder T(n) = nlogn beträgt.

HeapSort() benötigt logn schlechteste Zeit für jedes Element, und n Elemente machen seine Zeitkomplexität auch nlogn. Sowohl die Zeitkomplexität für den Aufbau des Heaps als auch für die Heap-Sortierung werden addiert und ergeben die resultierende Komplexität als nlogn. Daher ist die gesamte Zeitkomplexität in der Größenordnung von [Big Theta]: O(nlogn).

• Schlimmster Fall

Die Zeitkomplexität im schlimmsten Fall ist [Big O]: O(nlogn).

• Bester Fall

Die Zeitkomplexität im besten Fall ist [Big Omega]: O(nlogn). Sie ist identisch mit der Zeitkomplexität im schlimmsten Fall.

Raumkomplexität

Die Platzkomplexität für den Heap-Sortieralgorithmus ist O(1), da außer den temporären Variablen kein zusätzlicher Speicher benötigt wird.