Absteigende Heap-Sortierung mit Min-Heap

Heap Sort – Heap Sort ist ein vergleichsbasierter Algorithmus, der eine binäre Baumdatenstruktur verwendet, um eine Liste von Zahlen in aufsteigender oder absteigender Reihenfolge zu sortieren. Es erstellt eine Heap-Datenstruktur durch Heap-Sortierung, wobei die Wurzel das kleinste Element ist, entfernt dann die Wurzel und sortiert erneut, wobei die zweitkleinste Zahl in der Liste an der Wurzelposition entsteht.

Min Heap – Ein Min Heap ist eine Datenstruktur, bei der der übergeordnete Knoten immer kleiner als der untergeordnete Knoten ist, sodass der Wurzelknoten das kleinste Element unter allen Elementen ist.

Problemstellung

Gegeben ist ein Array von ganzen Zahlen. Sortieren Sie sie in absteigender Reihenfolge mit Min-Heap.

Beispiel 1

Input: [2, 5, 1, 7, 0]

Output: [7, 5, 2, 1, 0]

Beispiel 2

Input: [55, 1, 23, 10, 1]

Output: [55, 23, 10, 1, 1]

Methode 1

Um eine Heap-Sortierung in absteigender Reihenfolge mithilfe von Min-Heap durchzuführen, erstellen wir einen Min-Heap von Elementen und extrahieren jeweils ein Element, um durch Umkehren der Reihenfolge ein Array in absteigender Reihenfolge zu erhalten.

Pseudocode

procedure heapSort (arr[], n)
   Initialize priority queue: minHeap
   for i = 1 to n
      add arr[i] to minHeap
   i = n - 1
   while minHeap is not empty
      arr[i–] = top element of minHeap
      Remove the top element of minHeap
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm sortieren wir das Array mit Min-Heap und kehren dann die Reihenfolge um, um das Ergebnis zu erhalten.

#include <bits/stdc++.h>
using namespace std;
// Function to heap sort in decreasing order using min heap
void heapSort(int arr[], int n){

   // Creating min heap using a priority queue
   priority_queue<int, vector<int>, greater<int> > minHeap;
   
   // Inserting input array to min heap
   for (int i = 0; i < n; i++){
      minHeap.push(arr[i]);
   }
   
   // Iterating backwards in the input array, where each element is replaced by the smallest element extracted from min heap
   int i = n - 1;
   while (!minHeap.empty()){
      arr[i--] = minHeap.top();
      minHeap.pop();
   }
}
int main(){
   int arr[6] = {5, 2, 9, 1, 5, 6};
   int n = 6;
   heapSort(arr, n);
   cout << "Sorted array : ";
   for (int i = 0; i < n; i++){
      cout << arr[i] << " ";
   }
   cout << endl;
   return 0;
}

Ausgabe

Sorted array : 9 6 5 5 2 1

Zeitkomplexität - O(nlogn)

Raumkomplexität - O(n)

Methode 2

Eine weitere Lösung für dieses Problem besteht darin, einen Min-Heap zu erstellen, beginnend mit dem letzten Nicht-Blatt-Wurzelmuster und rückwärts arbeitend. Anschließend können wir das Array sortieren, indem wir den Wurzelknoten und den letzten Blattknoten austauschen und dann die Min-Heap-Eigenschaft wiederherstellen.

Pseudocode

procedure heapify (arr[], n , i)
   smallest = i
   l = 2i + 1
   r = 2i + 2
   if l < n and arr[l] < arr[smallest]
      smallest = l
   end if
   if r < n and arr[r] < arr[samllest]
      smallest = r
   end if
   if smallest is not i
      swap arr[i] to arr[smallest]
      heapify (arr, n, smallest)
   end if
end procedure

procedure heapSort (arr[], n)
   for i = n/2 - 1 to 0
      heapify(arr, n, i)
   for i = n-1 to 0
      swap arr[0] to arr[i]
      heapify (arr, i, 0)
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm verwenden wir die Funktion heapify(), um die Min-Heap-Eigenschaften des am Index i verwurzelten Teilbaums wiederherzustellen, und verwenden heapSort(), um den Min-Heap in umgekehrter Reihenfolge zu erstellen.

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

// Restores the min heap property of subtree rooted at index i
void heapify(int arr[], int n, int i){
   int smallest = i;
   int l = 2 * i + 1;
   int r = 2 * i + 2;
   if (l < n && arr[l] < arr[smallest]){
      smallest = l;
   }
   if (r < n && arr[r] < arr[smallest]){
      smallest = r;
   }
   if (smallest != i){
      swap(arr[i], arr[smallest]);
      heapify(arr, n, smallest);
   }
}
void heapSort(int arr[], int n){

   // Build the min heap in reverse order
   for (int i = n / 2 - 1; i >= 0; i--){
      heapify(arr, n, i);
   }
   
   // Sort the array by repeatedly swapping the root node with the last leaf node
   for (int i = n - 1; i >= 0; i--){
      swap(arr[0], arr[i]);
      heapify(arr, i, 0);
   }
}
int main(){
   int arr[6] = {5, 2, 9, 1, 5, 6};
   int n = 6;
   heapSort(arr, n);
   cout << "Sorted array : ";
   for (int i = 0; i < n; i++){
      cout << arr[i] << " ";
   }
   cout << endl;
   return 0;
}

Ausgabe

Sorted array : 9 6 5 5 2 1

Mit der vorherigen Methode zum Erstellen eines Min-Heaps mithilfe der Funktion heapSort() können wir dieselbe Methode in dieser Lösung verwenden, aber anstatt Heapify zum Wiederherstellen der Eigenschaften des Min-Heaps zu verwenden, verwenden wir zum Erstellen den herkömmlichen Hep-Sortieralgorithmus Amin-Heap und Die Reihenfolge der sortierten Elemente ist aufsteigend und wird weiter umgekehrt, um die gewünschte Ausgabe zu erhalten.

Pseudocode

procedure heapSort (arr[], n)
   for i = n/2 - 1 to 0
   parent = i
      while parent *2+1 < n
         child = parent*2+1
         if child+1 < n and arr[child] >arr[child+1]
            child = child + 1
         end if
         if arr[parent] > arr[child]
            swap arr[parent] to arr[child]
            parent = child
         else
            break
         end if
   for i = n-1 to 0
      swap arr[0] to arr[i]
      parent = 0
      while parent*2+1 < i
            child = parent*2+1
         if child+1 < n and arr[child] >arr[child+1]
            child = child + 1
         end if
         if arr[parent] > arr[child]
            swap arr[parent] to arr[child]
            parent = child
         else
            break
         end if
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm ändern wir den Heap-Sortieralgorithmus, um das Array in absteigender Reihenfolge zu sortieren.

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

void heapSort(int arr[], int n){
   // Building min heap in reverse order
   for (int i = n / 2 - 1; i >= 0; i--) {
   
      // Starting from last parent node, apply heapify operation
      int parent = i;
      while (parent * 2 + 1 < n) {
         int child = parent * 2 + 1;
         if (child + 1 < n && arr[child] > arr[child + 1]){
            child++;
         }
         if (arr[parent] > arr[child]){
            swap(arr[parent], arr[child]);
            parent = child;
         }
         else{
            break;
         }
      }
   }
   
   // Extarct elekemnhts form min heap in decreasing order
   for (int i = n - 1; i > 0; i--){
      swap(arr[0], arr[i]);
      int parent = 0;
      
      // Perform heapify operation at new root node
      while (parent * 2 + 1 < i){
         int child = parent * 2 + 1;
         if (child + 1 < i && arr[child] > arr[child + 1]){
            child++;
         }
         if (arr[parent] > arr[child]){
            swap(arr[parent], arr[child]);
            parent = child;
         }
         else {
            break;
         }
      }
   }
}
int main(){
   int arr[6] = {5, 2, 9, 1, 5, 6};
   int n = 6;
   heapSort(arr, n);
   cout << "Sorted array : ";
   for (int i = 0; i < n; i++) {
      cout << arr[i] << " ";
   }
   cout << endl;
   return 0;
}

Ausgabe

Sorted array : 9 6 5 5 2 1

Fazit

Zusammenfassend lässt sich sagen, dass wir zum Durchführen einer absteigenden Heap-Sortierung mit Min-Heap mehrere Methoden verwenden können, von denen einige eine zeitliche Komplexität von O(nlogn) haben und jede Methode eine unterschiedliche räumliche Komplexität aufweist.

Das obige ist der detaillierte Inhalt vonAbsteigende Heap-Sortierung mit Min-Heap. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!