Min Heap(paid)

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 in the best c++ online course 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]+" ");
        }
    }

    }

Previous post Heap Operations(paid)
Next post Points Collision(paid)

Leave a Reply

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