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

王林转载: 2023-08-29 15:49:07 282浏览

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

堆排序 - 堆排序是一种基于比较的算法，它使用二叉树数据结构按升序或降序对数字列表进行排序。它通过堆排序创建一个堆数据结构，其中根是最小元素，然后删除根，再次排序在根位置给出列表中第二小的数字。

最小堆 - 最小堆是一种数据结构，其中父节点始终小于子节点，因此根节点是所有元素中最小的元素。

问题陈述

给定一个整数数组。使用最小堆按降序对它们进行排序。

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