CSCI 330 Lab:: Priority Queue

Complete the implementation of the my_priority_queue template class as defined below, so that it is based on a heap structure, and runs correctly with the test code test_my_priority_queue.cpp. Note that my_priority_queue depends on the my_vector template class completed in an earlier lab.

#ifndef MY_PRIORITY_QUEUE_H
#define MY_PRIORITY_QUEUE_H

// my_priority_queue.h  -- a priority_queue implemented as a heap

#include "my_vector.h"
using namespace std;

template <class T> 
class my_priority_queue
{
public:
   typedef T value_type;
   my_priority_queue();
   bool empty();
   unsigned int size();
   void push(const T & x); 
   void pop(); 
   T & top();

private:
   my_vector<T> c;
};

#endif

---

#include <iostream>
#include <string>
#include <queue>
#include <cassert>
#include "my_priority_queue.h"

using namespace std;

int main(char *args[])
{
   //#define PRIORITY_QUEUE priority_queue
   #define PRIORITY_QUEUE my_priority_queue
   PRIORITY_QUEUE<int> pq;

   assert(pq.size() == 0);
   assert(pq.empty());

   pq.push(10);
   assert(pq.top() == 10);

   pq.push(20);
   assert(pq.top() == 20);

   pq.push(30);
   assert(pq.top() == 30);

   pq.push(40);
   assert(pq.top() == 40);

   pq.push(50);
   assert(pq.top() == 50);

   pq.push(5);
   assert(pq.top() == 50);

   pq.pop();
   assert(pq.top() == 40);

   pq.pop();
   assert(pq.top() == 30);

   pq.pop();
   assert(pq.top() == 20);

   pq.pop();
   assert(pq.top() == 10);

   pq.pop();
   assert(pq.top() == 5);

   pq.pop();
   assert(pq.size() == 0);

   PRIORITY_QUEUE<int> pq2;
   pq2.push(30);
   pq2.push(11);
   pq2.push(7);
   pq2.pop();
   assert(pq2.top() == 11);
   pq2.pop();
   assert(pq2.top() == 7);
   pq2.pop();
   assert(pq2.empty());

   cout << "All tests passed." << endl;
   cin.get();
}