Heap-Sortierung

Harshit Jindal 12 Oktober 2023
  1. Heap-Sortieralgorithmus
  2. Beispiel für Heap-Sortierung
  3. Implementierung des Heap-Sortieralgorithmus
  4. Komplexität des Heap-Sortieralgorithmus
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

Heap-Sortieralgorithmus

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

HeapSort()

  • Bauen Sie einen maximalen Heap mit den Elementen auf, die im Array A vorhanden sind.
  • Führen Sie für jedes Element, beginnend mit dem letzten Element in A, Folgendes durch.
  • Das Wurzelelement A[0] wird das maximale Element enthalten, tauschen Sie es mit diesem Element aus.
  • Verringern Sie die Heap-Größe um eins und Heapify() den maximalen Heap, wobei das letzte Element entfernt wird.

Heapify()

  • Initialisiere parent index mit dem Index des aktuellen Elements.
  • Berechne leftChild als 2*i+1 und rightChild als 2*i+2.
  • Wenn das Element am leftChild größer ist als der Wert am parent-Index, setzen Sie parent-Index auf leftChild.
  • Wenn das Element am rightChild größer ist als der Wert an parent index setze parent index auf rightChild.
  • Wenn sich der Wert des parent-Index in den letzten beiden Schritten geändert hat, dann tausche parent mit dem aktuellen Element und heapify rekursiv den parent-Index-Teilbaum. Ansonsten ist die Heap-Eigenschaft bereits erfüllt.

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:
Swap(A[5],A[0]) 4 3 5 2 1 6
Heapify() 5 3 4 2 1 6
  • Zweite Iteration:
Swap(A[4],A[0]) 1 3 4 2 5 6
Heapify() 4 3 1 2 5 6
  • Dritte Iteration:
Swap(A[3],A[0]) 2 3 1 4 5 6
Heapify() 3 2 1 4 5 6
  • Vierte Iteration:
Swap(A[2],A[0]) 1 2 3 4 5 6
Heapify() 2 1 3 4 5 6
  • Fünfte Iteration:
Swap(A[1],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6
  • Sechste Iteration:
Swap(A[0],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6

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.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Verwandter Artikel - Sort Algorithm