QUESTIONS 1,2. IN C++ 1) Using a heap, implement the priority queue. The class s
ID: 3765826 • Letter: Q
Question
QUESTIONS 1,2.
IN C++
1) Using a heap, implement the priority queue. 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. As an example, if entry [ 7 ] was the 33rd item added to the priority queue then order [ 7 ] would be 33. When you are comparing two entries with equal priority, use the order number to "BREAK THE TIE"( so that if two entries have the same priority number, then the one with the earlier order number will come out of the priority queue first)
2) Implment same thing with NO predefined limit on the size of the heap but USING A DYNAMIC ARRAY.
Explanation / Answer
/*
* C++ Program to Implement Priority Queue
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int priority;
int info;
struct node *link;
};
/*
* Class Priority Queue
*/
class Priority_Queue
{
private:
node *front;
public:
Priority_Queue()
{
front = NULL;
}
/*
* Insert into Priority Queue
*/
void insert(int item, int priority)
{
node *tmp, *q;
tmp = new node;
tmp->info = item;
tmp->priority = priority;
if (front == NULL || priority < front->priority)
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while (q->link != NULL && q->link->priority <= priority)
q=q->link;
tmp->link = q->link;
q->link = tmp;
}
}
/*
* Delete from Priority Queue
*/
void del()
{
node *tmp;
if(front == NULL)
cout<<"Queue Underflow ";
else
{
tmp = front;
cout<<"Deleted item is: "<<tmp->info<<endl;
front = front->link;
free(tmp);
}
}
/*
* Print Priority Queue
*/
void display()
{
node *ptr;
ptr = front;
if (front == NULL)
cout<<"Queue is empty ";
else
{ cout<<"Queue is : ";
cout<<"Priority Item ";
while(ptr != NULL)
{
cout<<ptr->priority<<" "<<ptr->info<<endl;
ptr = ptr->link;
}
}
}
};
/*
* Main
*/
int main()
{
int choice, item, priority;
Priority_Queue pq;
do
{
cout<<"1.Insert ";
cout<<"2.Delete ";
cout<<"3.Display ";
cout<<"4.Quit ";
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>item;
cout<<"Enter its priority : ";
cin>>priority;
pq.insert(item, priority);
break;
case 2:
pq.del();
break;
case 3:
pq.display();
break;
case 4:
break;
default :
cout<<"Wrong choice ";
}
}
while(choice != 4);
return 0;
}
using dynamic array
#include <iostream>
using namespace std;
class priorityQueue
{
private:
int front;
int rear;
int size;
int *array;
public:
priorityQueue();
~priorityQueue();
void insert(int x);
//remove and return the smallest item currently in the priority queue
int extractMin();
bool empty();
};
priorityQueue::priorityQueue()
{
front = rear = -1;
size = 10;
array = new int[size];
}
priorityQueue::~priorityQueue()
{
delete[] array;
}
void priorityQueue::insert(int x)
{
//if queue is full
if ( (rear + 1)% size == front ){
return;
}
//else if queue is empty
else if ( empty() ){
rear = front = 0;
}
else
{
rear = (rear + 1) % size;
}
array[rear] = x;
}
//extract and return smallest value in queue
int priorityQueue::extractMin()
{
int minValue = array[front];
if ( empty() ){
return -1;
}
else if (front == rear){
front = rear = -1;
}
else
{
front = (front + 1) % size;
}
//find smallest value
for (int i = front; i <= rear; i++){
if (array[i] < minValue)
minValue = array[i];
}
//return smallest value
return array[front];
}
bool priorityQueue::empty()
{
if ( (front == -1) && (rear == -1) )
return true;
else
return false;
}
int main()
{
priorityQueue myqueue;
myqueue.insert(4);
myqueue.insert(3);
myqueue.insert(2);
myqueue.insert(1);
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
myqueue.insert(8);
myqueue.insert(7);
myqueue.insert(6);
myqueue.insert(5);
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
system("pause");
return 0;
}