Heap Sort for decreasing order using min heap

Last Updated on July 20, 2022 by Ria Pathak

Problem Statement:

In this problem, we have given an array, and we have to sort the array in decreasing order using a min-heap.

Example:

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

What is Heap?

A heap is a complete binary tree, A complete binary tree is a binary tree in which all the levels are completely filled except the last level i.e. leaf node.

What is a Heap Sort Algorithm?

Heap Sort is a popular sorting Algorithm that processes the element by creating the min-heap or max-heap using the given array. Min-heap or max-heap represents the ordering of the array; the value of the root element will represent the minimum or maximum element of the array.

The basic concept of heap sort is to eliminate the elements one by one from the heap and then insert them in a sorted manner.

How to “heapify” a tree?

So, we can modify the tree in the max heap or min-heap. In other words, we can say, The reshaping of a binary tree into a heap tree is called heapify.

Min – Heap follows the property of a complete binary tree in which the value of the internal node is smaller than or equal to the value of the children of that node.
In 0 – based indexing, the node stored at k index in the array will have its left child held at index 2k + 1 and its right child at index 2k + 2.

Approach:

• The idea is quite simple, we will build a min-heap of the given array.
• And, perform the heapify method on the tree.
• In heapify, we’ll compare the root node with both the children.
• And perform the swap operation according to the min-heap condition.

Algorithm:

• Build a min-heap from the given input array.
• After this, the smallest node is stored at the root of the heap. Replace it with the last node of the heap until the size of the heap gets 1.
• Heapify the root of the tree.
• Repeat the above steps while the size of the heap is greater than 1.

Dry Run:

Code Implementation

#include <iostream> 
using namespace std; 
  
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) 
{ 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    for (int i = n - 1; i >= 0; i--) { 
        swap(arr[0], arr[i]); 
  
        heapify(arr, i, 0); 
    } 
} 
  
void printArray(int arr[], int n) 
{ 
    for (int i = 0; i < n; ++i) 
        cout << arr[i] << " "; 
    cout << " "; 
} 
  
int main() 
{ 
    int arr[] = { 1,50,100,25 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is "; 
    printArray(arr, n); 
} 

import java.io.*;
 
class Prepbytes {
     
    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 (l < n && arr[l] < arr[smallest])
            smallest = l;
 
        if (r < n && arr[r] < arr[smallest])
            smallest = r;
 
        if (smallest != i) {
            int temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = temp;
 
            heapify(arr, n, smallest);
        }
    }
 
    static void heapSort(int arr[], int n)
    {
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
 
        for (int i = n - 1; i >= 0; i--) {
             
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
 
            heapify(arr, i, 0);
        }
    }
 

    static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    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);
    }
}

def heapify(arr, n, i):
    smallest = i 
    l = 2 * i + 1 
    r = 2 * i + 2 
 
    if l < n and arr[l] < arr[smallest]:
        smallest = l
 
    if r < n and arr[r] < arr[smallest]:
        smallest = r
 
    if smallest != i:
        (arr[i],
         arr[smallest]) = (arr[smallest],
                           arr[i])
 
        heapify(arr, n, smallest)
 
def heapSort(arr, n):
     
    for i in range(int(n / 2) - 1, -1, -1):
        heapify(arr, n, i)
 
    for i in range(n-1, -1, -1):
         
        arr[0], arr[i] = arr[i], arr[0]
 
        heapify(arr, i, 0)
 
def printArray(arr, n):
     
    for i in range(n):
        print(arr[i], end = " ")
    print()
 
if __name__ == '__main__':
    arr = [4, 6, 3, 2, 9]
    n = len(arr)
 
    heapSort(arr, n)
 
    print("Sorted array is ")
    printArray(arr, n)

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).

This article tried to discuss How to implement a min heap to decrease the order of elements. Hope this blog helps you understand the concept. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.