1. MIN HEAP
#include<iostream.h>
#include<math.h>
#include<stdio.h>
#include<conio.h>
//#include<stdarg.h>
//using namespace std;
template <class T>
class minheap
{
private:
T *heap;
int capacity;
int size;
public:
//constructor
minheap(int cap)
{
heap=new T[cap];
capacity=cap;
size=0;
}
void insert(T& item);
void deletemin();
void display();
};
//function to insert an element in min heap
/*
argument 1 - the item to be inserted
*/
template <class T>
void minheap<T>::insert(T& item)
{
int i;
if(size==capacity)
cout<"Can't insert. Heap is full\n";
else
{
size=size+1;
i=size;
while((i>1)&(heap[i/2]>item))
{
if(heap[i/2]>item)
heap[i]=heap[i/2];
i=i/2;
}
heap[i]=item;
}
}
//function to display the elements in min heap
template <class T>
void minheap<T>::display()
{
int levelNum=1;
int thisLevel=0;
int gap=16;
for( int i=1; i<=size; i++)
{
for(int j=0; j<gap-1; j++)
cout<" ";
if(thisLevel != 0)
{
for(int j=0; j<gap-2; j++)
cout<" ";
}
//if(sizeof(heap[i])==1)
if(heap[i]==1)
cout<" ";
cout<heap[i];
thisLevel++;
if(thisLevel == levelNum)
{
cout<"\n\n";
thisLevel = 0;
levelNum *=2;
gap/=2;
}
}
cout<"\n\n";
if(thisLevel !=0)
{
cout<"\n\n";
}
}
//function to delete the minimum element
template <class T>
void minheap<T>::deletemin()
{
T del;
int temp,min=0,i=1,pos;
del=heap[1];
temp=heap[size];
//structure property
size=size-1;
heap[1]=temp;
//checking for heap order property
while(((2*i)<=size)||(((2*i)+1)<=size))
{
//finding min child of node i
min=heap[2*i];
pos=2*i;
if(((2*i)+1)<=size)
{
if(min>heap[(2*i)+1])
{
min=heap[(2*i)+1];
pos=(2*i)+1;
}
}
//if both the child are less than element inserted at i
if(min>heap[i])
{
cout<"Deleted element is "<del<endl;
return;
}
else
{
//swapping during perculate down
temp=heap[pos];
heap[pos]=heap[i];
heap[i]=temp;
}
i=pos;
} cout<"Deleted element is "<del<endl;
cout<"Deleted element is"<del<endl;
}
//application file
int main()
{
minheap<int> mh(15);
int num,opt,i,n;
char ch;
clrscr();
cout<"Enter the number of elements to be inserted\n";
cin>n;
for(i=0;i<n;i++)
{
cout<"Enter the element to be inserted :";
cin>num;
mh.insert(num);
}
cout<"Enter 1.Insert\n2.Display\n3.Delete\n";
do
{
cout<"Enter option : ";
cin>opt;
switch(opt)
{
case 1:
cout<"Enter the element to be inserted :";
cin>num;
mh.insert(num);
break;
case 2:
mh.display();
break;
case 3:
mh.deletemin();
mh.display();
break;
}
cout<"Enter y to continue : ";
cin>ch;
}while(ch=='y');
}
OUTPUT
Enter the number of elements to be inserted
4
Enter the element to be inserted :3
Enter the element to be inserted :5
Enter the element to be inserted :7
Enter the element to be inserted :9
Enter 1.Insert
2.Display
3.Delete
Enter option : 2
3
5 7
9
Enter y to continue : y
Enter option : 3
Deleted element is 3
5
9 7
Enter y to continue :n