Last Updated on March 31, 2022 by Ria Pathak
CONCEPTS USED:
Heaps.
DIFFICULTY LEVEL:
Easy.
PROBLEM STATEMENT(SIMPLIFIED):
Given an array containing N integers, your task is:
- To create min-heap(Insert elements one by one).
- Extract the minimum element from the heap created in the first step and print it.
- Print the extracted element and updated heap after extraction, separated by space.
Note: Use heap concepts to solve the problem.
See original problem statement here
For Example :
MIN-HEAP:
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]:
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);
}
void del()
{
prio_queue[0]=prio_queue[ind];
ind--;
percolatedown(0);
}
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);
}printf("%d ",prio_queue[0]);
del();
for(int i=0;i<n-1;i++)
printf("%d ",prio_queue[i]);
printf("\n");
}
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// write your code here
/* 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()+" ");
System.out.println(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]+" ");
}
}
}
#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);
}
void del()
{
prio_queue[0]=prio_queue[ind];
ind--;
percolatedown(0);
}
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);
}
cout<<prio_queue[0]<<" ";
del();
for(int i=0;i<n-1;i++)
cout<<prio_queue[i]<<" ";
cout<<"\n";
}
return 0;
}
[forminator_quiz id="2382"]
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.