Isih timbunan menurun menggunakan timbunan min

Isih Timbunan - Isih Timbunan ialah algoritma berasaskan perbandingan yang menggunakan struktur data pokok binari untuk mengisih senarai nombor dalam tertib menaik atau menurun. Ia mencipta struktur data timbunan dengan menyusun timbunan di mana akar adalah elemen terkecil, kemudian mengalih keluar akar dan mengisih semula pada kedudukan akar memberikan nombor terkecil kedua dalam senarai.

Timbunan Min - Timbunan min ialah struktur data di mana nod induk sentiasa lebih kecil daripada nod anak, jadi nod akar ialah elemen terkecil antara semua elemen.

Pernyataan Masalah

Diberikan tatasusunan integer. Isih mereka dalam tertib menurun menggunakan timbunan min.

Contoh 1

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

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

Contoh 2

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

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

Kaedah 1

Untuk melaksanakan isihan timbunan dalam tertib menurun menggunakan timbunan min, kami mencipta timbunan min unsur dan mengekstrak satu elemen pada satu masa untuk mendapatkan tatasusunan dalam tertib menurun dengan membalikkan tertib.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam atur cara berikut, kami mengisih tatasusunan menggunakan timbunan min dan kemudian membalikkan susunan untuk mendapatkan hasilnya.

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

Output

Sorted array : 9 6 5 5 2 1

Kerumitan masa - O(nlogn)

Kerumitan ruang - O(n)

Kaedah 2

Satu lagi penyelesaian untuk masalah ini ialah membina timbunan min bermula dari corak akar bukan daun terakhir dan bekerja ke belakang. Kemudian kita boleh mengisih tatasusunan dengan menukar nod akar dan nod daun terakhir, dan kemudian memulihkan sifat timbunan min.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam atur cara berikut, kami menggunakan fungsi heapify() untuk memulihkan sifat timbunan min subpokok yang berakar pada indeks i, dan menggunakan heapSort() untuk membina timbunan min dalam susunan terbalik.

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

Output

Sorted array : 9 6 5 5 2 1

Menggunakan kaedah sebelumnya untuk mencipta timbunan min menggunakan fungsi heapSort(), kami boleh menggunakan kaedah yang sama dalam penyelesaian ini, tetapi daripada menggunakan heapify untuk memulihkan sifat timbunan min, kami menggunakan algoritma pengisihan hep tradisional untuk mencipta timbunan amin dan Susunan elemen yang diisih adalah menaik dan seterusnya diterbalikkan untuk mendapatkan output yang diingini.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program berikut, kami mengubah suai algoritma isihan timbunan untuk mengisih tatasusunan dalam tertib menurun.

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

Output

Sorted array : 9 6 5 5 2 1

Kesimpulan

Ringkasnya, untuk melaksanakan isihan timbunan menurun menggunakan timbunan min, kita boleh menggunakan berbilang kaedah, sesetengah daripadanya mempunyai kerumitan masa O(nlogn) dan setiap kaedah mempunyai kerumitan ruang yang berbeza.

Atas ialah kandungan terperinci Isih timbunan menurun menggunakan timbunan min. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!