Thursday, October 22, 2009

priority queue

#include "iostream.h"
#include "conio.h"
#include "iomanip.h"
#define MAX 10
class pqueue
{
int pq[MAX];
int mh;
public:
pqueue();

int size(void){ return mh;}
int isempty(void) {
if(mh == 0)
return 1;
return 0;}
int pop(void);
void push(int);
void display(void);
int top(void){
if(!isempty()) return pq[1];
else cout<<"\n PQ empty"; return 0;}
};
pqueue::pqueue()
{
for(int i = 0; i < MAX; i++,pq[i] = 0);
mh = 0;
}
void pqueue::push(int ele) {
int cpos = ++mh;
while(cpos != 1 && pq[cpos/2] < ele) {
pq[cpos] = pq[cpos/2];
cpos /= 2; }
pq[cpos] = ele;

}
int pqueue::pop(void) {
if(!isempty()) {
int le = pq[mh--];
pq[0] = pq[1];
int cnode = 1;
int child = 2;
while(child<= mh) {
if(child < mh && pq[child] child++;
if(le >= pq[child])
break;
pq[cnode] = pq[child];
cnode = child;
child *= 2;
}
pq[cnode] = le;
return pq[0];
}
else {
cout<<"\n Queue is Empty ";
return 0;
}

}

void pqueue::display(void) {
if(!isempty()) {
cout<<"\n The elements in the queue :"< for(int i = 1; i <= mh; i++)
cout< else cout<<"\n Queue is empty";
}
int menu(void) {
cout<<"\n\tMENU"< cout<<"\n 1 -> push \n 2 -> pop \n ";
cout<<"3 ->isempty \n 4 -> Display";
cout<<"\n 5 ->topelement \n 6 -> size \n ";
cout<<"\n 7 -> Heap Sort \n 8 -> exit ";
cout<<"\n Enter your choice :";
int ch;
cin>>ch;
return ch;
}
void heapsort(void) {
int n,ele;
pqueue q;
cout<<"\n Enter the no.of elements :";
cin>>n;
cout<<"\n Enter the elements : \n";
for(int i = 0; i < n; i++) {
cin>>ele;
q.push(ele);
}
cout<<"\n The elements in the sorted order is :\n";
for(i = 0 ; i < n; i ++)
cout<}
void main() {
int ch,ele;
pqueue p;
do {
clrscr();
ch = menu();
switch(ch){
case 1: cout<<"\n Enter the element to push : ";
cin>>ele;
p.push(ele); break;
case 2: ele = p.pop();
if(ele)
cout<<"\n The popped element is :"< break;
case 3: if(p.isempty())
cout<<"\n queue is empty" ;
else
cout<<"\n queue is not empty ";
break;
case 4: p.display(); break;
case 5: ele = p.top();
cout<<"\n The top element is :"< break;
case 6: cout<<"\n No.of elements is :"< break;
case 7: heapsort(); break;
case 8: break;
Default:cout<<"\n Invalid Choice. Try again ";
} getch();

}while (ch != 8);
}

No comments:

Post a Comment