C++ 使用最小堆进行递减排序的堆排序

堆排序 - 堆排序是一种基于比较的算法，它使用二叉树数据结构以递增或递减的顺序对数字列表进行排序。它通过堆排序创建一个堆数据结构，其中根节点是最小元素，然后移除根节点，再次排序以获取列表中第二小的数字放在根节点位置。

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

问题陈述

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

示例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来恢复最小堆的属性，我们使用传统的堆排序算法来创建一个最小堆，并对元素按递增顺序进行排序，然后再反转以获得所需的输出。

伪代码

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