Descending heap sort using min-heap

Heap Sort - Heap sort is a comparison-based algorithm that uses a binary tree data structure to sort a list of numbers in ascending or descending order. It creates a heap data structure by heap sorting where the root is the smallest element, then removes the root and sorts again giving the second smallest number in the list at the root position.

Min Heap - A min heap is a data structure in which the parent node is always smaller than the child node, so the root node is the smallest element among all elements.

Problem Statement

Given an array of integers. Sort them in descending order using min-heap.

Example 1

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

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

Example 2

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

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

method 1

To perform a heap sort in descending order using a min-heap, we create a min-heap of elements and extract one element at a time to get an array in descending order by reversing the order.

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

Example: C implementation

In the following program, we sort the array using min-heap and then reverse the order to get the result.

#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

Time complexity - O(nlogn)

Space complexity - O(n)

Method 2

Another solution to this problem is to build a min-heap starting from the last non-leaf root pattern and working backwards. We can then sort the array by swapping the root node and the last leaf node, and then restore the min-heap property.

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

Example: C implementation

In the following program, we use the heapify() function to restore the min-heap properties of the subtree rooted at index i, and use heapSort() to build the min-heap in reverse order.

#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

Using the previous method of creating a min-heap using the heapSort() function, we can use the same method in this solution, but instead of using heapify to restore the properties of the min-heap, we use the traditional hep sorting algorithm to create amin The order of heap and sorted elements is incremented and further reversed to obtain the desired output.

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

Example: C implementation

In the following program, we modify the heap sort algorithm to sort the array in descending order.

#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

in conclusion

In summary, in order to perform a descending heap sort using a min-heap, we can use a variety of methods, some of which have a time complexity of O(nlogn), and each method has a different space complexity.

The above is the detailed content of Descending heap sort using min-heap. For more information, please follow other related articles on the PHP Chinese website!