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

### 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.