Operations on Min Heap | Walmart | Synopsys

Operations on Min Heap | Walmart | Synopsys

Question

Write a program to perform Operations on Min Heap. The Operations are Insert, delete, ExtractMin. This is asked in Walmart, Sysnopsys, Amazon, Ola Cabs, etc.

 

Min Heap

A Min heap is a binary tree such that – the data contained in each node is less than (or equal to) the data in that node’s children.

  • Use an array to hold the data.
  • Store the root in position 1.We won’t use index 0 for this implementation.
  •  For any node in position i,
    – its left child (if any) is in position 2i
    – its right child (if any) is in position 2i + 1

Logic

  1. Removing from a heap
  • Place the root element in a variable to
    return later.
  • Remove the last element in the deepest
    level and move it to the root.
  • Check for Heap Order, whether all root is smaller than its child.

2. Inserting into heap

  • Place the new element in the next available
    position in the array.
  • Calculate N =count/2 and check for the Heap order.

Program

#include<stdio.h>
int heap[20]={0};//heap array intialized to zero
int count=0;     //no. of items in heap
int main()
{
    int ch,num;
    while(1)
    {
        printf("\n1.Insert key");
        printf("\n2.Delete key");
        printf("\n3.Extract Min");
        printf("\n4.Print heap");
        printf("\n5.Exit");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: printf("Enter the element to be inserted..");
                    scanf("%d",&num);
                    count++;
                    Insert(num);break;
            case 2: Delete();break;
            case 3: printf("The Min is %d",heap[1]);break;
            case 4: Print();break;
            case 5: printf("Have a nice day");exit(-1);
            default: printf("wrong choice");
        }
    }
}
void Delete()
{
    int i,N;

    printf("Deleted..%d",heap[1]);
    heap[1]= heap[count];           //Copy last element to first element
    heap[count]=0;                  //assign 0 to last element
    count--;                        //item deleted so decrement count
    N = count;
    /*Check whether the heap is in order*/
    for(i=1;i<N;i++)
    {
        HeapOrder(i);
    }
}
void Print()
{
    int i;
    if(heap[1]==0)
    {
        printf("Heap is empty");
        return;
    }
    /*Print the heap array*/
    for(i=1;i<=count;i++)
    {
        printf("%d: %d ",i,heap[i]);
    }
}
void swap(int* x,int* y)
{
    int temp;
    temp= *x;
    *x=*y;
    *y=temp;
}
void HeapOrder(int i)
{
    if(heap[i*2]!=0)                    //left not empty
        {
            if(heap[i*2+1]!=0)          //right child not empty
            {
                /*Find the smallest of right or left child
                 and compare that with root node and swap if root node is larger
                */
                if(heap[i*2]<heap[i*2+1])
                {
                    if(heap[i*2]<heap[i])
                    {
                        swap(&heap[i*2],&heap[i]);
                    }
                }
                else
                {
                    if(heap[i*2+1]<heap[i] )
                    {
                        swap(&heap[i*2+1],&heap[i]);
                    }
                }
            }
            /*Only left child present*/
            else if(heap[i*2]<heap[i])
            {
                swap(&heap[i*2],&heap[i]);
            }
        }
}
void Insert(int num)
{
    int N,i,temp;
    heap[count] = num;
    N = count/2;                    //no.of items divide by 2
    /*Check whether heap is in order*/
    for(i=N;i>=1;i--)               //Loop from N to 1 index
    {
        HeapOrder(i);
    }
}

Suggested Reading…

No of identical digit showed by digital clock | Infosys

Employee management using File in C

 

Sree Hari Sanjeev

The founder and CEO of Wisdom Overflow. His enthusiasm and effort has taken the blog to next level. You will be motivated just by taking a look at his daily schedule.

Leave a Reply

Your email address will not be published.

one × four =