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