使用最小堆進行降序的堆排序

堆排序 - 堆排序是一種基於比較的演算法，它使用二元樹資料結構按升序或降序對數字列表進行排序。它透過堆排序創建一個堆資料結構，其中根是最小元素，然後刪除根，再次排序在根位置給出列表中第二小的數字。

最小堆 - 最小堆是一種資料結構，其中父節點始終小於子節點，因此根節點是所有元素中最小的元素。

問題陳述

給定一個整數數組。使用最小堆按降序對它們進行排序。

範例 1

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

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

範例 2

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

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

方法 1

為了使用最小堆按降序執行堆排序，我們建立一個元素的最小堆，並一次提取一個元素，透過反轉順序得到一個按降序排列的陣列。

虛擬程式碼

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

範例：C 實作

在下面的程式中，我們使用最小堆對陣列進行排序，然後反轉順序以獲得結果。

#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

時間複雜度 - O(nlogn)

空間複雜度 - O(n)

方法2

該問題的另一個解決方案是從最後一個非葉根模式開始並向後建立一個最小堆。然後我們可以透過交換根節點和最後一個葉子節點來對陣列進行排序，然後恢復最小堆屬性。

虛擬程式碼

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

範例：C 實作

在下面的程式中，我們使用 heapify() 函數來恢復以索引 i 為根的子樹的最小堆屬性，並使用 heapSort() 以相反的順序建立最小堆。

#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

使用先前使用heapSort() 函數建立最小堆的方法，我們可以在這個解決方案中使用相同的方法，但不是使用heapify 來恢復最小堆的屬性，而是使用傳統的hep 排序演算法來建立amin堆和排序元素的順序遞增，並進一步反轉以獲得所需的輸出。

虛擬程式碼

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

範例：C 實作

在下面的程式中，我們修改堆排序演算法以降序對陣列進行排序。

#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

結論

總之，為了使用最小堆執行降序堆排序，我們可以使用多種方法，其中一些方法的時間複雜度為 O(nlogn)，每種方法的空間複雜度各不相同。

以上是使用最小堆進行降序的堆排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！