Heap Sort - Le tri par tas est un algorithme basé sur la comparaison qui utilise une structure de données arborescente binaire pour trier une liste de nombres par ordre croissant ou décroissant. Il crée une structure de données en tas par tri en tas où la racine est le plus petit élément, puis supprime la racine et trie à nouveau en donnant le deuxième plus petit nombre de la liste à la position racine.
Min Heap - Un tas min est une structure de données dans laquelle le nœud parent est toujours plus petit que le nœud enfant, de sorte que le nœud racine est le plus petit élément parmi tous les éléments.
Étant donné un tableau d’entiers. Triez-les par ordre décroissant en utilisant 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]
Pour effectuer un tri par tas par ordre décroissant à l'aide de min-heap, nous créons un min-tas d'éléments et extrayons un élément à la fois pour obtenir un tableau par ordre décroissant en inversant l'ordre.
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
Dans le programme suivant, nous trions le tableau à l'aide de min-heap, puis inversons l'ordre pour obtenir le résultat.
#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
Complexité temporelle - O(nlogn)
Complexité spatiale - O(n)
Une autre solution à ce problème consiste à créer un min-heap en commençant par le dernier motif racine non-feuille et en travaillant à rebours. Nous pouvons ensuite trier le tableau en échangeant le nœud racine et le dernier nœud feuille, puis restaurer la propriété min-heap.
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
Dans le programme suivant, nous utilisons la fonction heapify() pour restaurer les propriétés du tas min du sous-arbre enraciné à l'index i, et utilisons heapSort() pour construire le tas min dans l'ordre inverse.
#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
En utilisant la méthode précédente de création d'un tas min à l'aide de la fonction heapSort(), nous pouvons utiliser la même méthode dans cette solution, mais au lieu d'utiliser heapify pour restaurer les propriétés du tas min, nous utilisons l'algorithme de tri hep traditionnel pour créer tas amin et l'ordre des éléments triés est croissant et inversé pour obtenir le résultat souhaité.
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
Dans le programme suivant, nous modifions l'algorithme de tri par tas pour trier le tableau par ordre décroissant.
#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
En résumé, afin d'effectuer un tri par tas décroissant à l'aide de min-heap, nous pouvons utiliser plusieurs méthodes, dont certaines ont une complexité temporelle de O(nlogn) et chaque méthode a une complexité spatiale différente.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Comment acheter et vendre du Bitcoin en Chine
Comment formater le disque dur sous Linux
Comment entrer les privilèges root sous Linux
Quels sont les moyens de dégager les flotteurs ?
Comment utiliser Redis comme serveur de cache
Comment résoudre l'exception de lecture de fichiers volumineux Java
qu'est-ce qui est okx
Quelles informations privées les amis proches de Douyin verront-ils ?
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
