Data Structures Implementation Of Heap Tree Using C++

[+] Post Title :

Data Structures Implementation Of Heap Tree Using C++

[+] Date : Monday 21 October 2013
[+] Author : ravi
[+] Type : heap tree

#include<iostream.h>
#include<conio.h>
#include<math.h>
class heap
{
public:
int *a,pos,size;
public:
heap()
{
int i;
cout<<"\n enter size \n";
cin>>size;
a=new int[size];
pos=0;
for(i=0;i<size;i++)
a[i]=-1;
}

void insert()
{
if(pos<size)
{
cout<<"\n enter element \n";
cin>>a[pos++];
}
else
{
cout<<"\n overflow -- Cannot insert \n";
}
int k=pos-1;
while(k>0)
{
if(a[k]>a[((int)ceil((k)/2.0))-1])
{
swap(&a[k],&a[((int)ceil((k)/2.0))-1]);
k=((int)ceil((k)/2.0))-1;
}
else
break;
}
cout<<"\n inserted value successfully \n";
}


void remove()
{
a[0]=a[pos-1];
a[pos-1]=-1;
pos--;
int i=0;
while( (a[2*i+1]!=-1) && (a[2*i+2]!=-1) && (a[i]<a[2*i+1] || a[i]<a[2*i+2]) )
{
if(a[2*i+1]>a[2*i+2])
{
swap(&a[i],&a[2*i+1]);
i=2*i+1;
}
else
{
swap(&a[i],&a[2*i+2]);
i=2*i+2;
}
}
cout<<"\n Parent element deleted and tree adjusted successfully \n";
}

void display()
{
int i;
for(i=0;i<size;i++)
{
if(2*i+1<size && a[2*i+1]!=-1 && a[2*i+2]!=-1)
{
cout<<"\n Parent is "<<a[i]<<" left is "<<a[2*i+1]<<" right is "<<a[2*i+2]<<"\n";
}
if(a[2*i+1]!=-1 && a[2*i+2]==-1)
{
cout<<"\n Parent is "<<a[i]<<" left is "<<a[2*i+1]<<"\n";
}
if(a[i]!=-1 && a[2*i+1]==-1 && a[2*i+2]==-1)
{
cout<<"\n Leaf node is "<<a[i]<<"\n";
}
}
}

void swap(int *x, int *y)
{
cout<<"\n swapping values "<<*x<<"and "<<*y<<"\n";
int temp;
temp=*x;
*x=*y;
*y=temp;
}

};

void main()
{
heap k;
int i=0,s;
clrscr();
while(i!=1)
{
cout<<"\n ************** M  E  N  U ************** \n";
cout<<" Enter 1.insert  2.delete 3.display 4.exit \n";
cin>>s;
switch(s)
{
case 1:
k.insert();
break;
case 2:
k.remove();
break;
case 3:
k.display();
break;
case 4:
i=1;
}
}
getch();
}