C++: Using a heap, implement this priority queue class. The class should have a

Question

C++: Using a heap, implement this priority queue class. The class should have a static constant member variable, CAPACITY, which is the maximum size of the heap and an array, data, that contains the heap with the entries. We also want to have FIFO behavior for entries with equal priority. To obtain this behavior, the class should have an extra private member variable that is an array, order, where order[i] contains the order in which data[i] was added to the queue. For example, if entry[7] was the 23rd item added to the priority queue, then order[7] would be 23. When you are comparing two entries with equal priority, use the order number to “break the tie” (so that if 2 entries have the same priority number, then the one with the earlier order num. will come out of the priority queue 1st).

// FILE: queuel.h (part of the namespace main_savitch_8B) // TEMPLATE CLASS PROVIDED: queue (a queue of items) // TEMPLATE PARAMETER, TYPEDEFS, and MEMBER CONSTANTS for the queue class: //The template parameter, Item, is the data type of the items in the queue, also defined /as queue::value type. It may be any of the C++ built-in types (int, char, etc.), or a //class with a default constructor, a copy constructor, and an assignment operator. The //definition queue:size type is the data type of any variable that keeps track of how // many items are in a queue. The static const CAPACITY is the maximum capacity of a // queue for this first queue implementation. // CONSTRUCTOR for the queuedtem template class: queue ( ) Postcondition: The queue has been initialized as an empty queue. // MODIFICATION MEMBER FUNCTIONS for the queue template class: // void popC) Precondition: size()> 0. Postcondition: The top item of the queue has been removed //vOid push(const Item& entry) Postcondition: A new copy of entry has been inserted at the rear of the queue. // CONSTANT MEMBER FUNCTIONS for the queue template class: / b bool empty() const Postcondition: The return value is true if the queue is empty. (continued)

Explanation / Answer

#include<iostream.h>
#include<process.h>
#include<math.h>
#include<iomanip.h>
#include<malloc.h>
struct Heap
{
int capacity;
int size;
int *node;
};
typedef struct Heap *pqueue;
pqueue initialize(int max)
{
pqueue heap;
if(max<3)
{
cout<<“ Priority Queue is too Small ”;
exit(0);
}
heap = new Heap;
if(heap==NULL)
{
cout<<“ Out of Space ”;
exit(0);
}
heap->nodes=new int[((max+1) * sizeof(int))];
if(heap->nodes==NULL)
{
cout<<“ Out of Space ”;
exit(0);
}
heap->capacity = max;
heap->size=0;
heap->nodes[0]=0;
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<<“ Heap is Full ”;
return;
}
for(i=++heap->size; heap->nodes[i/2] > x; i/=2)
heap->nodes[i]=heap->nodes[i/2];
heap->nodes[i]=x;
}
int deletemin(pqueue heap)
{
int i, child, min, last;
if(isempty(heap))
{
cout<<“ Heap is Empty ”;
return heap->nodes[0];
}
min=heap->nodes[1];
last=heap->nodes[heap->size–];
for(i=1; i*2<=heap->size; i=child)
{
child = i*2;
if(child!=heap->size && heap->nodes[child+1]<heap->nodes[child])
child++;
if(last>heap->nodes[child])
heap->nodes[i]=heap->nodes[child];
else
break;
}
heap->nodes[i]=last;
return min;
}
void main()
{
int size,ch,ele,child;
pqueue heap;
cout<<“ Working with Priority Queues (or) Heaps ”;
cout<<“ Enter the Size of the Heap…”;
cin>>size;
heap = initialize(size);
do
{
cout<<“ Menu ”;
cout<<“ 1. Insert”;
cout<<“ 2. Delete”;
cout<<“ 3. Display”;
cout<<“ 4. Exit”;
cout<<“ Enter Your Choice…”;
cin>>ch;
switch(ch)
{
case 1:
cout<<“ enter element …”;
cin>>ele;
insert(ele, heap);
break;
case 2:
ele=deletemin(heap);
cout<<“ the deleted element is “<<ele<<endl;
break;
case 3:
int space,level=1;
int c=1;
for(int k=1; k<heap->size; k++)
{
for(int j=1;j<=level;j++)
{
if(c<=heap->size)
{
space=(int) (heap->size*2)/c;
cout<<setw(space)<<” “<<heap->nodes[c++]<<setw(space)<<” “;
}
else
break;
}
if (level==1)
level=2;
else if (level>=2)
level=level*2;
cout<<“ ”;
}
break;
default:
cout<<“ Exit “;
}
}while(ch<4);
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.