Write Code In C++ 5-1 Motivation: This project is to implement Priority Queue, u

Question

Write Code In C++

5-1 Motivation: This project is to implement Priority Queue, using array or a complete binary tree structure. Details about priority queue can be found from http://www.cse.cuhk.edu.hk/~taoyf/course/2100sum11/lec8.pdf

5-2 Requirements: You should name your Prority Queue class as PQ. The queue must be able to hold unlimited number of integers. It has two key operations: Push and Pop, which should have the time complexity of O(logn).

5-3 Files to turn in: You need to turn in four files: makefile, main.C, PQ.C, PQ.h. You should have a main.C that reads in or generates some integers, pushes them into the PQ one by one, and pops and prints them until the PQ is empty.

5-4 Grading The total points is 12, you will get full credit if you correctly implement it using tree structure, 6 points if you correctly implement it using array. No late turn in is acceptable, any late turn in will be given 0 point. Your code must be compilable on Linux/Unix, any code that cannot be compiled by g++ will automatically get ZERO point.

Use This Main File:

#include <iostream>

#include "PQ.h"

#include <stdlib.h> /* for random number generation */

#include <time.h> /* time for random seed*/

using namespace std;

int main(){

PQ pq;

/* initialize random seed: */

srand (time(NULL));

for (int i = 1; i < 10; ++i) pq.Push(rand() % 100 + 1);

Node * p = pq.tail;

while(p != pq.head){

cout << p->val << endl;

p = p->prev;

}

for (int i = 0; i < 10; i++) cout << pq.Pop() << ", ";

}

Explanation / Answer

PQ.C

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
priority_queue<int> pq;
int choice, item;
while (1)
{
cout<<"Priority Queue"<<endl;
cout<<"1.Insert Element into the Priority Queue"<<endl;
cout<<"2.Delete Element from the Priority Queue"<<endl;
cout<<"3.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
pq.push(item);
break;
case 2:
item = pq.top();
if (!pq.empty())
{
pq.pop();
cout<<"Element "<<item<<" Deleted"<<endl;
}
else
{
cout<<"Priority Queue is Empty"<<endl;
}
break;
case 3:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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