43. PRIORITY QUEUE USING HEAP

//PRIORITY QUEUE USING HEAP

#include<iostream.h>
#include<process.h>
#include<math.h>
#include<iomanip.h>
#include<malloc.h>

struct Heap
{
int capacity;
int size;
int *element;
};

typedef struct Heap *pqueue;

pqueue initialize(int max)
{
pqueue heap;
if(max<3)
{
cout<<”\nPriority Queue is too Small\n”;
exit(0);
}
heap = new Heap;
if(heap==NULL)
{
cout<<”\nOut of Space\n”;
exit(0);
}
heap->elements=new int[((max+1) * sizeof(int))];
if(heap->elements==NULL)
{
cout<<”\n Out of Space\n”;
exit(0);
}
heap->capacity = max;
heap->size=0;
heap->elements[0]=0; //minData
return heap;
}

int isempty(pqueue heap)
{
return (heap->size==0);
}

int isfull(pqueue heap)
{
return(heap->size==heap->capacity);
}

void insert(int x, pqueue heap)
{
int i;
if(isfull(heap))
{
cout<<”\nHeap is Full\n”;
return;
}
for(i=++heap->size; heap->elements[i/2] > x; i/=2)
heap->elements[i]=heap->elements[i/2];
heap->elements[i]=x;
}

int deletemin(pqueue heap)
{
int i, child, min, last;
if(isempty(heap))
{
cout<<”\nHeap is Empty\n”;
return heap->elements[0];
}
min=heap->elements[1];
last=heap->elements[heap->size--];
for(i=1; i*2<=heap->size; i=child)
{
child = i*2;
if(child!=heap->size && heap->elements[child+1]<heap->elements[child])
child++;
if(last>heap->elements[child])
heap->elements[i]=heap->elements[child];
else
break;
}
heap->elements[i]=last;
return min;
}

void main()
{
int size,ch,ele,child;
pqueue heap;
cout<<”\nWorking with Priority Queues (or) Heaps\n”;
cout<<”\nEnter the Size of the Heap…”;
cin>>size;
heap = initialize(size);
do
{
cout<<”\n\t\tMenu\n”;
cout<<”\n1. Insert”;
cout<<”\n2. Delete”;
cout<<”\n3. Display”;
cout<<”\n4. Exit”;
cout<<”\nEnter Your Choice…”;
cin>>ch;
switch(ch)
{
case 1:
cout<<”\nEnter an Element…”;
cin>>ele;
insert(ele, heap);
break;
case 2:
ele=deletemin(heap);
cout<<”\nDeleted Element is “<<ele<<endl;
break;
case 3:
int space,level=1;
int c=1;
for(int i=1; i<heap->size; i++)
{
for(int j=1;j<=level;j++)
{
if(c<=heap->size)
{
space=(int) (heap->size*2)/c;
cout<<setw(space)<<”  “<<heap->elements[c++]<<setw(space)<<”  “;

}
else
break;
}
if (level==1)
level=2;
else if (level>=2)
level=level*2;
cout<<”\n”;
}
break;
default:
cout<<”\n Exit “;
}
}while(ch<4);
}