Question

Implement the minimum priority queue UnsortedMPQ (using vector) that is a child class of the provided MPQ class. The functions from MPQ that are virtual function (remove min(), is empty(), min(), and insert()) must be implemented in the child classes. The functions remove min() and min() should throw an exception if the minimum priority queue is empty.

For the UnsortedMPQ class, you will use a vector to implement the minimum priority queue functions. The insert() function should be O(1) and the remove min() function should be O(n).

Below I will attach the parent class (MPQ.h), child class (unsortedMPQ.h - needs implementation), and unsortedMPQ-main.cpp - for testing and does not need to be implemented.

Please Code in C++.

MPQ.h

#ifndef MPQ_H
#define MPQ_H

//Abstract Minimum Priority Queue Class
template
class MPQ{
public:
virtual T remove_min() = 0;
virtual T min() = 0;
virtual bool is_empty() = 0;
virtual void insert(const T& data) = 0;
};
#endif

unsortedMPQ.h

#ifndef UNSORTEDMPQ_H
#define UNSORTEDMPQ_H

#include
#include
#include "MPQ.h"

/*
* Minimum Priority Queue based on a vector
*/
template
class UnsortedMPQ: MPQ {

};

#endif

unsortedMPQ-main.cpp (for testing)

#include "UnsortedMPQ.h"
#include

using namespace std;

int main() {
{
UnsortedMPQ mpq;
cout << "Inserting 1 - 5" << endl;
mpq.insert(1);
mpq.insert(2);
mpq.insert(3);
mpq.insert(4);
mpq.insert(5);
cout << "Remove min five times" << endl;
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << endl << endl;
}
{
UnsortedMPQ mpq;
cout << "Inserting 5 - 1" << endl;
mpq.insert(5);
mpq.insert(4);
mpq.insert(3);
mpq.insert(2);
mpq.insert(1);
cout << "Remove min five times" << endl;
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << endl << endl;
}
{
UnsortedMPQ mpq;
cout << "Inserting mixed order 1-5" << endl;
mpq.insert(5);
mpq.insert(2);
mpq.insert(4);
mpq.insert(3);
mpq.insert(1);
cout << "Remove min five times" << endl;
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << endl << endl;
}
{
UnsortedMPQ mpq;
cout << "Testing exception" << endl;
try {
mpq.remove_min();
}
catch (exception& e) {
cout << e.what() << endl;
}
cout << endl;
}
{
UnsortedMPQ mpq;
cout << "Inserting mixed order 1-5" << endl;
mpq.insert(5);
mpq.insert(2);
mpq.insert(4);
mpq.insert(3);
mpq.insert(1);
cout << "Remove min five times" << endl;
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << endl;
cout << "Inserting mixed order 11-15" << endl;
mpq.insert(15);
mpq.insert(12);
mpq.insert(14);
mpq.insert(13);
mpq.insert(11);
cout << "Remove min five times" << endl;
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << ", ";
cout << mpq.remove_min() << endl;
cout << "Testing exception" << endl;
try {
mpq.remove_min();
}
catch (exception& e) {
cout << e.what() << endl;
}
}
return 0;
}

Answer 1

Pic 1

Pic 2

Pic 3

Pic 4

Here I had attached 4 pictures of coding in C++ compiler. You can run and execute once as same as i had done. follow all steps one by one.