Heap Operations

CONCEPTS USED:

Heaps.

DIFFICULTY LEVEL:

Easy.

PROBLEM STATEMENT(SIMPLIFIED):

Given an array containing N integers, your task is:

  1. To create min-heap(Insert elements one by one).
  2. Extract the minimum element from the heap created in the first step and print it.
  3. 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.

Leave a Reply

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