Last Updated on March 23, 2022 by Ria Pathak
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, 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() :
- Insert the item at the last index, and increment the size by 1.
- Then, check if the inserted item is smaller than its parent,
- If yes, then swap the inserted item with its parent.
- If no, then do nothing.
- Now, go to step
2and repeat untill we reach root (first element).
Heap Sort():
- Replace the root node with the farthest right node (last element).
- Fix the last node position and perform heapify with the remaining nodes.
- Repeat untill each node is fixed.
Heapify ():
- if the heap property holds true then you are done.
- else if
- the replacement node value <= its parent nodes value
then swap them, and repeat step 3.- else
- 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);
}
}
}
[forminator_quiz id="1566
This article tried to discuss Heaps. Hope this blog helps you understand and solve the problem. To practice more problems on Heaps you can check out MYCODE | Competitive Programming.