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
- 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
[code lang=”c”]
#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);
}
}
[/code]
Suggested Reading…
No of identical digit showed by digital clock | Infosys
Employee management using File in C