Tri par tas décroissant à l'aide de min-heap

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.

Énoncé du problème

Étant donné un tableau d’entiers. Triez-les par ordre décroissant en utilisant min-heap.

Exemple 1

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

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

Exemple 2

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

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

Méthode 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.

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

Exemple : implémentation C++

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;
}

Sortie

Sorted array : 9 6 5 5 2 1

Complexité temporelle - O(nlogn)

Complexité spatiale - O(n)

Méthode 2

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.

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

Exemple : implémentation C++

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;
}

Sortie

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é.

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

Exemple : implémentation C++

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;
}

Sortie

Sorted array : 9 6 5 5 2 1

Conclusion

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!