HEAP_TREE

HOME

  /*   PROGRAM TO IMPLEMENT HEAPTREE

#include "iostream.h"

#define SIZE 100

class heap
{
private:
int a[SIZE];
void siftup(int i);
void siftdown(int i);

public:
heap();
void build_heap();
void insert(int num);
int deletemin();
void put_data();
int empty();
};

heap::heap()
{
int i;
a[0] =0; // no. of elements in the heap
for(i=1; i<SIZE; i++)
a[i] = -1;
}

void heap::siftup(int i)
{ //i is the index of heap element to be sifted up
int temp = a[i];
int p = i/2; //parent index
while(temp1)
{
a[i] = a[p];
i =p;
p= i/2;
}
a[i] = temp;
}

void swap(int &a,int &b)
 {
 	int temp;

temp =a;
 	a = b;
 	b = temp;
 }

void heap::siftdown(int i)
 {
 	int lchild = 2*i;
 	int rchild = 2*i+1;

while(a[rchild] != -1)
 	{
 		if(a[lchild] < a[i] && a[lchild] <= a[rchild])
 		{
 			swap(a[lchild],a[i]);
 			i = lchild;
 			lchild = 2*i;
 			rchild = 2*i+1;
 		}
 	else if(a[rchild] < a[i]  && a[rchild] <a[lchild])
 		{
 			swap(a[rchild],a[i]);
 			i = rchild;
 			lchild = 2*i;
 			rchild = 2*i+1;
 		}
 		else
 			break;
 	}
 	if(a[lchild] != -1 && a[lchild] < a[i])
 		swap(a[lchild],a[i]);
 }

void heap::build_heap()
 {
 	int n,i;

cout<<endl<>n;
 	a[0] = n;
 	cout<<endl<<"enter the elements: ";
 //build complete binary tree
 	for(i=1; i>a[i];
 	//heapify the binary tree
 	for(i = n/2; i>=1; i--)
 		siftdown(i);
 }

 void heap::insert(int num)
 {
 	int n;
 	n =  ++a[0];
 	if(n > SIZE)
 	{
 cout<<"memory limit exceeded. no insertion performed.";
 		a[0]--;
 		return;
 	}
 	a[n] = num;
 	siftup(n);
 }

int heap::deletemin()
 {
 	int n,temp;
 	if(a[0] == 0)
 	{
 	cout<<"empty heap. no deletion possible.";
 		return -1;
 	}

temp = a[1];
 	n    = a[0]--;
 	a[1] = a[n];
 	siftdown(1);

return temp;
 }

void heap::put_data()
 {
 	int i;
 	cout<<endl;
 	cout<<"the heap is: ";
 	cout<<endl;
 	for(i=1; i<=a[0]; i++)
 		cout<<"  "<<a[i];
 }

int heap::empty()
 {
 	if(a[0] == 0)
 		return 1;
 	return 0;
 }

void main()
{
int x;
heap h;
h.build_heap();
h.put_data();
cout<<endl<>x;
h.insert(x);
cout<<endl<<"after insertion: ";
h.put_data();
cout<<endl<<endl<<"minimum element deleted: ";
x = h.deletemin();
cout<<x<<endl;
cout<<"after deletion: ";
h.put_data();
}
//PROGRAM ENDS
/*OUTPUT:

enter no. of elements in the heap: 9enter the elements: 18 2 13 10 15 3 7 16 8

the heap is:
   2  8  3  10  15  13  7  16  18
 enter the element to insert: 4

after insertion:
 the heap is:
   2  4  3  10  8  13  7  16  18  15

minimum element deleted: 2
 after deletion:
 the heap is:
   3  4  7  10  8  13  15  16  18
   Press any key to continue */


HOME