Heap Sort

Concepts Used:

Heap

Difficulty Level:

Easy

Problem Statement :

Given an array containing N integers, our task is to create a min-heap using the elements of the given array and sort the array in descending order using heap sort.

See original problem statement here

Solution Approach :

Introduction :

Idea is to create a min-heap then replace the root with the last element. Now that the least valued element is stored at the last position, we will heapify the remaining elements (or node) & repeat the process for all elements.

Method 1:

Sort the array in increasing order using any sorting algoritm which can be learnt from some online coding courses, now print the array staring from the last position (reverse order).

Method 2 :

In a min-heap, the root always stores the smaller value as compared to its left & right subtree, this condition needs to be true for every node. We need to insert each item one by one such that it's parent is always smaller than the item itself. If the parent is greater, then we need to swap the current item with its parent.

In order to sort this min-heap in decreasing order, we need to replace the root value with the last value and fix its position and perform heapify with the remaining nodes which are not fixed.
We will repeat this process untill all nodes are fixed.

Algorithms :

Insert() :

  1. Insert the item at the last index, and increment the size by 1.
  2. Then, check if the inserted item is smaller than its parent,
  3. If yes, then swap the inserted item with its parent.
  4. If no, then do nothing.
  5. Now, go to step 2 and repeat untill we reach root (first element).

Heap Sort():

  1. Replace the root node with the farthest right node (last element).
  2. Fix the last node position and perform heapify with the remaining nodes.
  3. Repeat untill each node is fixed.

Heapify ():

  1. if the heap property holds true then you are done.
  2. else if
  3. the replacement node value <= its parent nodes value
    then swap them, and repeat step 3.
  4. else
  5. swap the replacement node with the smallest child node, and
    repeat step 3.

Solutions:

#include <stdio.h>
int parent(int i)
{
return i/2;
}
int left(int i)
{
return i*2;
}
int right(int i)
{
return (i*2)+1;
}
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void insert(int heap[], int *size, int val)
{
int i = *size;
heap[i] = val;
(*size)++;
while( i!=1 && heap[parent(i)]<heap[i])
{
    swap(&heap[parent(i)],&heap[i]);
    i = parent(i);
}
}
void heapify(int heap[],int i, int size)
{
int l = left(i);
int r = right(i);
int s= i;
if(l<size && heap[l]< heap[i])
s = l;
if(r<size && heap[r]<heap[s])
s = r;

if(s!=i)
{
    swap(&heap[i],&heap[s]);
    heapify(heap,s,size);
}
}
void heapSort(int heap[], int n)
{
    // build heap (rearrange array)
    for (int i = n / 2 ; i >= 1; i--)
        heapify(heap,i,n);
    // one by one extract an element from heap
    for (int i=n-1; i>=1; i--)
    {
        // move current root to end
        swap(&heap[1], &heap[i]);
        // call max heapify on the reduced heap
        heapify(heap,1,i);
    }
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    int n;
    scanf("%d",&n);
    int size=1;
    int *heap = (int *)malloc(sizeof(int)*(n+1));
    while(n--)
    {
    int a;
    scanf("%d",&a);
    insert(heap,&size,a);
    }

    heapSort(heap,size);

    for(int i=1;i<size;i++)
    {
    printf("%d ",heap[i]);
    }
    printf("\n");
}

return 0;
}
#include <bits/stdc++.h>
using   namespace std;
int parent(int i)
{
    return i/2;
}
int left(int i)
{
    return i*2;
}
int right(int i)
{
    return (i*2)+1;
}   
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void insert(int heap[], int *size, int val)
{
    int i = *size;
    heap[i] = val;
    (*size)++;
    while( i!=1 && heap[parent(i)]<heap[i])
    {
    swap(&heap[parent(i)],&heap[i]);
    i = parent(i);
    }
}
void heapify(int heap[],int i, int size)
{
    int l = left(i);
    int r = right(i);
    int s= i;
    if(l<size && heap[l]< heap[i])
    s = l;
    if(r<size && heap[r]<heap[s])
    s = r;
    if(s!=i)
    {
    swap(&heap[i],&heap[s]);
    heapify(heap,s,size);
    }
}
void heapSort(int heap[], int n)
{
    // build heap (rearrange array)
    for (int i = n / 2 ; i >= 1; i--)
    heapify(heap,i,n);
    // one by one extract an element from heap
    for (int i=n-1; i>=1; i--)
    {
    // move current root to end
    swap(&heap[1], &heap[i]);
    // call max heapify on the reduced heap
    heapify(heap,1,i);
    }
}
int main()
{
    int t;
    cin>t;
    while(t--)
    {
    int n;
    cin>n;
    int size=1;
    int *heap = (int*)malloc(sizeof(int)*(n+1));
    while(n--)
    {
    int a;
    cin>a;
    insert(heap,&size,a);
    }

    heapSort(heap,size);

    for(int i=1;i<size;i++)
    cout<<heap[i]<<" ";
    cout<<endl;
    }
    return 0;
}
import java.util.*;
public class Main
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 
        // 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 max heapify on the reduced heap 
            heapify(arr, i, 0); 
        } 
    } 
    // 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 largest = i; // Initialize largest as root 
        int l = 2*i + 1; // left = 2*i + 1 
        int r = 2*i + 2; // right = 2*i + 2 
        // If left child is larger than root 
        if (l < n && arr[l] < arr[largest]) 
            largest = l; 
        // If right child is larger than largest so far 
        if (r < n && arr[r] < arr[largest]) 
            largest = r; 
        // If largest is not root 
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap; 
            // Recursively heapify the affected sub-tree 
            heapify(arr, n, largest); 
        } 
    } 
    /* A utility function to print array of size n */
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
    // Driver program 
    public static void main(String args[]) 
    { 
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t-->0)
    {
        int n = sc.nextInt();
        int []arr = new int[n];
        for(int i=0;i<n;i++)
        {
        arr[i] = sc.nextInt();
        }
        Main ob = new Main(); 
        ob.sort(arr); 
        //System.out.println("Sorted array is"); 
        printArray(arr); 
    }
    } 
} 
Previous post Minimum Difference
Next post Print first K non-repeating characters of a string

Leave a Reply

Your email address will not be published. Required fields are marked *