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

CONCEPTS USED:

Heaps.

DIFFICULTY LEVEL:

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 {
        // 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()+" ");
            // 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.

Leave a Reply

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