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.
Gegeben ist ein Array von ganzen Zahlen. Sortieren Sie sie in absteigender Reihenfolge mit Min-Heap.
Input: [2, 5, 1, 7, 0]
Output: [7, 5, 2, 1, 0]
Input: [55, 1, 23, 10, 1]
Output: [55, 23, 10, 1, 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.
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
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;
}
Sorted array : 9 6 5 5 2 1
Zeitkomplexität - O(nlogn)
Raumkomplexität - O(n)
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.
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
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;
}
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.
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
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;
}
Sorted array : 9 6 5 5 2 1
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!
