Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Min Heap

Last Updated on March 31, 2022 by Ria Pathak

Heaps.

Easy.

### PROBLEM STATEMENT(SIMPLIFIED):

Given an array containing N integers, your task is to create a min-heap using the elements of the given array and print the heap array. Elements needs to be inserted one by one in the heap.
Note: Use heap concepts to solve the problem.

See original problem statement here

#### For Example :

``````Sample Input
2
5
3 2 4 1 5
4
4 2 3 4

Sample Output
1 2 4 3 5
2 4 3 4``````

### MIN-HEAP:

``````            15                     13
/      \               /       \
18        25           20         35
/                      /  \        /  \
30                     41    51    100   41``````

A Min-Heap is a complete binary tree in which the value in each internal node is smaller than or equal to the values in the children of that node.
Mapping the elements of a heap into an array is trivial: if a node is stored a index k, then its left child is stored at index 2k + 1 and its right child at index 2k + 2.

How is Min Heap represented?

A Min Heap is a Complete Binary Tree. A Min heap is typically represented as an array. The root element will be at Arr[0]. For any ith node, i.e., Arr[i]:

``````Arr[(i -1) / 2] returns its parent node.
Arr[(2 * i) + 1] returns its left child node.
Arr[(2 * i) + 2] returns its right child node.``````

### SOLUTION:

```#include <stdio.h>
#include <string.h>
#include<stdlib.h>
int prio_queue[1000005];int ind=-1;
void percolateup(int pos)
{
if(pos<1)
return ;
int par=(pos-1)/2;
if(prio_queue[par]>prio_queue[pos])
{
int temp=prio_queue[par];
prio_queue[par]=prio_queue[pos];
prio_queue[pos]=temp;
percolateup(par);
}
}
void percolatedown(int pos)
{
int left=2*pos+1,right=2*pos+2,min=pos;
if(left<=ind)
{
if(prio_queue[pos]>prio_queue[left])
min=left;
}
if(right<=ind)
{
if(prio_queue[min]>prio_queue[right])
min=right;
}
if(pos!=min)
{
int temp=prio_queue[min];
prio_queue[min]=prio_queue[pos];
prio_queue[pos]=temp;
percolatedown(min);
}
}
void insert(int x)
{
prio_queue[++ind]=x;
percolateup(ind);
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
ind=-1;
int n;scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x;scanf("%d",&x);
insert(x);
}
for(int i=0;i<n;i++)
printf("%d ",prio_queue[i]);
printf("\n");
}
return 0;
}
```
``` #include <bits/stdc++.h>
using namespace std;

int prio_queue[1000005];int ind=-1;
void percolateup(int pos)
{
if(pos<1)
return ;
int par=(pos-1)/2;
if(prio_queue[par]>prio_queue[pos])
{
int temp=prio_queue[par];
prio_queue[par]=prio_queue[pos];
prio_queue[pos]=temp;
percolateup(par);
}
}
void percolatedown(int pos)
{
int left=2*pos+1,right=2*pos+2,min=pos;
if(left<=ind)
{
if(prio_queue[pos]>prio_queue[left])
min=left;
}
if(right<=ind)
{
if(prio_queue[min]>prio_queue[right])
min=right;
}
if(pos!=min)
{
int temp=prio_queue[min];
prio_queue[min]=prio_queue[pos];
prio_queue[pos]=temp;
percolatedown(min);
}
}
void insert(int x)
{
prio_queue[++ind]=x;
percolateup(ind);
}
int main()
{
int t;cin>>t;
while(t--)
{
ind=-1;
int n;cin>>n;
for(int i=0;i<n;i++)
{
int x;cin>>x;
insert(x);
}
for(int i=0;i<n;i++)
cout<<prio_queue[i]<<" ";
cout<<"\n";
}
return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
public static void main(String[] args) throws IOException {
/*  Scanner sc = new Scanner(new File("D:\\PrepByte\\Coding Platform\\Heap\\Easy\\HPSRT\\tc\\HPSRT_sample.in"));
Writer wr = new FileWriter("D:\\PrepByte\\Coding Platform\\Heap\\Easy\\HPSRT\\tc\\HPSRT_sample.out");*/
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t-->0) {
int n = sc.nextInt();
//int k = sc.nextInt();
MinHeap minHeap = new MinHeap(n);
for (int i = 0; i < n; i++) {
minHeap.insert(sc.nextInt());
}

// wr.write(minHeap.remove()+" ");
// minHeap.deleteKey(k);
minHeap.printHeap(sc);
// minHeap.heapSort(wr);
System.out.println();
//wr.write("\n");
}
//wr.flush();
//wr.close();

}

}
class MinHeap
{
private int[]Heap;
private int size;
private int maxSize;
private static final int FRONT = 1;
MinHeap(int maxSize)
{
this.maxSize = maxSize;
size=0;
Heap = new int[this.maxSize+1];
Heap[0] = Integer.MIN_VALUE;
}
private int parent(int pos) {
return pos / 2;
}
private int leftChild(int pos)
{
return (2*pos);
}
private int rightChild(int pos)
{
return (2*pos)+1;
}
private boolean isLeaf(int pos)
{
if(pos>=(size/2) && pos<=size)
return true;
return false;
}
private void swap(int fpos, int spos)
{
int temp;
temp = Heap[fpos];
Heap[fpos]=Heap[spos];
Heap[spos]=temp;
}
private void minHeapify(int pos)
{
int left = leftChild(pos);
int right = rightChild(pos);
int largest = pos;
if(left<=size && Heap[left]<Heap[largest])
largest=left;
if(right<=size && Heap[right]<Heap[largest])
largest = right;

if(largest!=pos)
{
swap(pos, largest);
minHeapify(largest);
}
/*if(!isLeaf(pos))
{
if(Heap[pos]>Heap[leftChild(pos)]
|| Heap[pos]>Heap[rightChild(pos)]){
if(Heap[leftChild(pos)]<Heap[rightChild(pos)])
{
swap(pos,leftChild(pos));
minHeapify(leftChild(pos));
}
else
{
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}*/
}
void insert(int element)
{
if(size>=maxSize)
return;

Heap[++size]=element;
int i=size;
while(Heap[i]<Heap[parent(i)])
{
swap(i,parent(i));
i=parent(i);
}
}
private void build_heap()
{
int j=(int)Math.floor(size/2.0);
for(int i=j;i>=1;i--){
minHeapify(i);
}

}
public void heapSort(Writer wr) throws IOException {
build_heap();
int length=size;
for(int i=size;i>=2;i--)
{
swap(1,i);
size--;
minHeapify(1);
}
size=length;
// printHeap(wr);

}
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size];
size=size-1;
minHeapify(FRONT);
return popped;
}
public void deleteKey(int i)
{
decreaseKey(i, Integer.MIN_VALUE);
remove();
}

private void decreaseKey(int i, int new_val) {
Heap[i]=new_val;
while(i !=0 && Heap[parent(i)]>Heap[i])
{
swap(i,parent(i));
i=parent(i);
}
}

void printHeap(Scanner sc) throws IOException {
for(int i=1;i<=size;i++)
{
//wr.write(Heap[i]+" ");
System.out.print(Heap[i]+" ");
}
}

}
```

[forminator_quiz id="2377"]

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.