Heap Sort for decreasing order using min heap

Last Updated : 24 Apr, 2023

Given an array of elements, sort the array in decreasing order using min heap.

Examples:

Input : arr[] = {5, 3, 10, 1}
Output : arr[] = {10, 5, 3, 1}

Input : arr[] = {1, 50, 100, 25}
Output : arr[] = {100, 50, 25, 1}

Prerequisite: Heap sort using min heap.

Algorithm :

Build a min heap from the input data.
At this point, the smallest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
Repeat above steps while size of heap is greater than 1.

Note: Heap Sort using min heap sorts in descending order where as max heap sorts in ascending order

Implementation:

C++

// C++ program for implementation of Heap Sort
#include <bits/stdc++.h>
using namespace std;
 
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
    int smallest = i; // Initialize smallest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2
 
    // If left child is smaller than root
    if (l < n && arr[l] < arr[smallest])
        smallest = l;
 
    // If right child is smaller than smallest so far
    if (r < n && arr[r] < arr[smallest])
        smallest = r;
 
    // If smallest is not root
    if (smallest != i) {
        swap(arr[i], arr[smallest]);
 
        // Recursively heapify the affected sub-tree
        heapify(arr, n, smallest);
    }
}
 
// main function to do heap sort
void heapSort(int arr[], int n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
 
    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        swap(arr[0], arr[i]);
 
        // call min heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
 
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}
 
// Driver program
int main()
{
    int arr[] = { 4, 6, 3, 2, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    heapSort(arr, n);
 
    cout << "Sorted array is \n";
    printArray(arr, n);
}

Java

// Java program for implementation of Heap Sort
 
import java.io.*;
 
class GFG {
     
    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    static void heapify(int arr[], int n, int i)
    {
        int smallest = i; // Initialize smallest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2
 
        // If left child is smaller than root
        if (l < n && arr[l] < arr[smallest])
            smallest = l;
 
        // If right child is smaller than smallest so far
        if (r < n && arr[r] < arr[smallest])
            smallest = r;
 
        // If smallest is not root
        if (smallest != i) {
            int temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = temp;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, n, smallest);
        }
    }
 
    // main function to do heap sort
    static void heapSort(int arr[], int n)
    {
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
 
        // One by one extract an element from heap
        for (int i = n - 1; i >= 0; i--) {
             
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
 
            // call min heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }
 
    /* A utility function to print array of size n */
    static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int arr[] = { 4, 6, 3, 2, 9 };
        int n = arr.length;
 
        heapSort(arr, n);
 
        System.out.println("Sorted array is ");
        printArray(arr, n);
    }
}
 
// This code is contributed by vt_m.

Python3

# Python3 program for implementation 
# of Heap Sort 
 
# To heapify a subtree rooted with 
# node i which is an index in arr[].
# n is size of heap 
def heapify(arr, n, i):
    smallest = i # Initialize smallest as root 
    l = 2 * i + 1 # left = 2*i + 1 
    r = 2 * i + 2 # right = 2*i + 2 
 
    # If left child is smaller than root 
    if l < n and arr[l] < arr[smallest]: 
        smallest = l 
 
    # If right child is smaller than 
    # smallest so far 
    if r < n and arr[r] < arr[smallest]: 
        smallest = r 
 
    # If smallest is not root 
    if smallest != i: 
        (arr[i], 
         arr[smallest]) = (arr[smallest],
                           arr[i])
 
        # Recursively heapify the affected
        # sub-tree 
        heapify(arr, n, smallest)
 
# main function to do heap sort 
def heapSort(arr, n):
     
    # Build heap (rearrange array) 
    for i in range(int(n / 2) - 1, -1, -1):
        heapify(arr, n, i) 
 
    # One by one extract an element
    # from heap 
    for i in range(n-1, -1, -1):
         
        # Move current root to end #
        arr[0], arr[i] = arr[i], arr[0]
 
        # call min heapify on the reduced heap 
        heapify(arr, i, 0)
 
# A utility function to print 
# array of size n 
def printArray(arr, n):
     
    for i in range(n):
        print(arr[i], end = " ") 
    print()
 
# Driver Code 
if __name__ == '__main__':
    arr = [4, 6, 3, 2, 9] 
    n = len(arr) 
 
    heapSort(arr, n) 
 
    print("Sorted array is ") 
    printArray(arr, n)
 
# This code is contributed by PranchalK

C#

// C# program for implementation of Heap Sort
using System;
 
class GFG {
     
    // To heapify a subtree rooted with 
    // node i which is an index in arr[],
    // n is size of heap
    static void heapify(int[] arr, int n, int i)
    {
        int smallest = i; // Initialize smallest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2
 
        // If left child is smaller than root
        if (l < n && arr[l] < arr[smallest])
            smallest = l;
 
        // If right child is smaller than smallest so far
        if (r < n && arr[r] < arr[smallest])
            smallest = r;
 
        // If smallest is not root
        if (smallest != i) {
            int temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = temp;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, n, smallest);
        }
    }
 
    // main function to do heap sort
    static void heapSort(int[] arr, int n)
    {
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
 
        // One by one extract an element from heap
        for (int i = n - 1; i >= 0; i--) {
             
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
 
            // call min heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }
 
    /* A utility function to print array of size n */
    static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
 
    // Driver program
    public static void Main()
    {
        int[] arr = { 4, 6, 3, 2, 9 };
        int n = arr.Length;
 
        heapSort(arr, n);
 
        Console.WriteLine("Sorted array is ");
        printArray(arr, n);
    }
}
 
// This code is contributed by vt_m.

Javascript

<script>
 
 
// Javascript program for implementation of Heap Sort
 
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
function heapify(arr, n, i)
{
    var smallest = i; // Initialize smallest as root
    var l = 2 * i + 1; // left = 2*i + 1
    var r = 2 * i + 2; // right = 2*i + 2
 
    // If left child is smaller than root
    if (l < n && arr[l] < arr[smallest])
        smallest = l;
 
    // If right child is smaller than smallest so far
    if (r < n && arr[r] < arr[smallest])
        smallest = r;
 
    // If smallest is not root
    if (smallest != i) {
        [arr[i], arr[smallest]] = [arr[smallest], arr[i]]
 
        // Recursively heapify the affected sub-tree
        heapify(arr, n, smallest);
    }
}
 
// main function to do heap sort
function heapSort(arr, n)
{
    // Build heap (rearrange array)
    for (var i = parseInt(n / 2 - 1); i >= 0; i--)
        heapify(arr, n, i);
 
    // One by one extract an element from heap
    for (var i = n - 1; i >= 0; i--) {
        // Move current root to end
        [arr[0], arr[i]] = [arr[i], arr[0]]
 
        // call min heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
 
/* A utility function to print array of size n */
function printArray(arr, n)
{
    for (var i = 0; i < n; ++i)
        document.write( arr[i] + " ");
    document.write("<br>");
}
 
// Driver program
var arr = [4, 6, 3, 2, 9];
var n = arr.length;
heapSort(arr, n);
document.write( "Sorted array is <br>");
printArray(arr, n);
 
 
 
</script>

Output

Sorted array is 
9 6 4 3 2

Time complexity:It takes O(logn) for heapify and O(n) for constructing a heap. Hence, the overall time complexity of heap sort using min heap or max heap is O(nlogn)
Space complexity: O(n) for call stack

New Approach

Build a min heap from the array elements.
Create an empty result array.
While the min heap is not empty:
a. Remove the minimum element from the heap.
b. Add the element to the beginning of the result array.
Return the result array.

C++

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<int> sortArrayInDescendingOrder(vector<int>& arr)
{
    priority_queue<int, vector<int>, greater<int> > minHeap;
 
    for (int num : arr) {
        minHeap.push(num);
    }
 
    vector<int> result;
    while (!minHeap.empty()) {
        int top = minHeap.top();
        minHeap.pop();
        result.insert(result.begin(), top);
    }
 
    return result;
}
 
int main()
{
    vector<int> arr = { 4, 6, 3, 2, 9 };
    vector<int> result = sortArrayInDescendingOrder(arr);
 
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
 
    return 0;
}
// This code is contributed by chinmaya121221

Java

import java.util.*;
 
public class Main {
    public static List<Integer>
    sortArrayInDescendingOrder(List<Integer> arr)
    {
        PriorityQueue<Integer> minHeap
            = new PriorityQueue<>();
 
        for (int num : arr) {
            minHeap.add(num);
        }
 
        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            int top = minHeap.poll();
            result.add(0, top);
        }
 
        return result;
    }
 
    public static void main(String[] args)
    {
        List<Integer> arr = Arrays.asList(4, 6, 3, 2, 9);
        List<Integer> result
            = sortArrayInDescendingOrder(arr);
 
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Python3

import heapq
 
 
def sortArrayInDescendingOrder(arr):
    minHeap = []
    for num in arr:
        heapq.heappush(minHeap, num)
 
    result = []
    while minHeap:
        top = heapq.heappop(minHeap)
        result.insert(0, top)
 
    return result
 
 
if __name__ == '__main__':
    arr = [4, 6, 3, 2, 9]
    result = sortArrayInDescendingOrder(arr)
 
    for num in result:
        print(num, end=' ')
    print()

C#

using System;
using System.Collections.Generic;
 
class Program {
    static List<int>
    SortArrayInDescendingOrder(List<int> arr)
    {
        PriorityQueue<int> minHeap
            = new PriorityQueue<int>();
 
        foreach(int num in arr) { minHeap.Push(num); }
 
        List<int> result = new List<int>();
        while (minHeap.Count > 0) {
            int top = minHeap.Top;
            minHeap.Pop();
            result.Insert(0, top);
        }
 
        return result;
    }
 
    static void Main(string[] args)
    {
        List<int> arr = new List<int>{ 4, 6, 3, 2, 9 };
        List<int> result = SortArrayInDescendingOrder(arr);
 
        foreach(int num in result)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}
 
class PriorityQueue<T> where T : IComparable<T> {
    private List<T> _heap;
 
    public int Count
    {
        get { return _heap.Count; }
    }
 
    public T Top
    {
        get { return _heap[0]; }
    }
 
    public PriorityQueue() { _heap = new List<T>(); }
 
    public void Push(T item)
    {
        _heap.Add(item);
        int i = _heap.Count - 1;
        while (i > 0
               && _heap[(i - 1) / 2].CompareTo(_heap[i])
                      > 0) {
            Swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
 
    public void Pop()
    {
        if (_heap.Count == 0)
            throw new InvalidOperationException(
                "PriorityQueue is empty");
 
        int lastIndex = _heap.Count - 1;
        _heap[0] = _heap[lastIndex];
        _heap.RemoveAt(lastIndex);
        lastIndex--;
 
        int i = 0;
        while (true) {
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;
            if (leftChild > lastIndex)
                break;
 
            int j = leftChild;
            if (rightChild <= lastIndex
                && _heap[rightChild].CompareTo(
                       _heap[leftChild])
                       < 0) {
                j = rightChild;
            }
 
            if (_heap[i].CompareTo(_heap[j]) <= 0)
                break;
 
            Swap(i, j);
            i = j;
        }
    }
 
    private void Swap(int i, int j)
    {
        T temp = _heap[i];
        _heap[i] = _heap[j];
        _heap[j] = temp;
    }
}
// This code is contributed by sarojmcy2e

Javascript

// JavaScript program to sort the array in descending order
 
function sortArrayInDescendingOrder(arr) {
    let minHeap = new MinHeap();
    // Push all elements to the min heap
    for (let num of arr) {
        minHeap.push(num);
    }
 
    let result = [];
    while (!minHeap.isEmpty()) {
        let top = minHeap.top();
        minHeap.pop();
        result.unshift(
            top); // Insert at the beginning of the array
    }
 
    return result;
}
 
class MinHeap {
    constructor() { this.heap = []; }
    push(num) {
        this.heap.push(num);
        this.bubbleUp(this.heap.length - 1);
    }
 
    pop() {
        let top = this.heap[0];
        let last = this.heap.pop();
 
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
 
        return top;
    }
 
    top() { return this.heap[0]; }
 
    isEmpty() { return this.heap.length === 0; }
 
    bubbleUp(index) {
        while (index > 0) {
            let parent = Math.floor((index - 1) / 2);
 
            if (this.heap[parent] > this.heap[index]) {
                [ this.heap[parent], this.heap[index] ] =
                    [ this.heap[index], this.heap[parent] ];
                index = parent;
            }
            else {
                break;
            }
        }
    }
 
    bubbleDown(index) {
        while (true) {
            let left = 2 * index + 1;
            let right = 2 * index + 2;
            let smallest = index;
 
            if (left < this.heap.length
                && this.heap[left] < this.heap[smallest]) {
                smallest = left;
            }
 
            if (right < this.heap.length
                && this.heap[right] < this.heap[smallest]) {
                smallest = right;
            }
 
            if (smallest !== index) {
                [ this.heap[index], this.heap[smallest] ] =
                    [
                        this.heap[smallest],
                        this.heap[index]
                    ];
                index = smallest;
            }
            else {
                break;
            }
        }
    }
}
 
// Driver code
let arr = [ 4, 6, 3, 2, 9 ];
 
// Function call
let result = sortArrayInDescendingOrder(arr);
console.log(result.join(" "));

Output

9 6 4 3 2

Time Complexity: O(n log n), where n is the number of elements in the array.
Auxiliary Space: O(1), because it sort the array in place without using extra space that depends on the input size .

Shashank_Pathak

Improve

Height of a complete binary tree (or Heap) with N nodes

Print all nodes less than a value x in a Min Heap.

Some other type of Heap

Easy problems on Heap

Medium problems on Heap

Hard problems on Heap

Heap Sort for decreasing order using min heap

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?