Heap Operations(paid)

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 referring the best sites to learn programming languages 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 3 4 5 
2 3 4 4 

Sample test case explanation
In the first test case output
1 ​is the minimum element
2,3,4,5 ​is the heap array after extraction.

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);
    }
    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;
    }

Previous post Parallelograming(paid)
Next post Min Heap(paid)

Leave a Reply

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