#ifndef _HEAP_H_ #define _HEAP_H_

#include #include

// This class implements an unbounded max heap.

// class invariant: heap property is satisfied for a max heap

template class heap { public: heap(); // postcondition: empty heap has been created unsigned int size() const; // postcondition: number of elements in a heap has been returned bool is_empty() const; // postcondtion: returned whether the heap is empty void insert (const T& item); // postcondition: item has been added void remove(); // precondition: heap is not empty // postcondition: largest item has been removed from the heap T max() const; // precondition: heap is not empty // postcondition: copy of largest element in the heap has been returned T& max(); // precondition: heap is not empty // postcondition: access to largest element in the heap has been returned private: std::vector v; unsigned int max_child (unsigned int index) const; // precondition: element at index has children // postcondition: index of the larger child has been returned // if there is only 1 child - index of that child has been returned };

#include "heap.template"

#endif // _HEAP_H_

#ifndef _PRIORITY_QUEUE_H #define _PRIORITY_QUEUE_H

#include "heap.h"

template class priority_queue { public: priority_queue(); // postcondition: empty priority_queue has been created void pop(); // precondition: priority_queue is not emtpy // postcondition: highest priority item has been removed void push (const T& item); // postcondition: item has been inserted bool empty () const; // postcondition: returned whether priority queue is empty unsigned int size() const; // postcondition: returned number of items in the priority queue T top() const; // precondition: priority queue is not empty // postcondition: copy of highest priority item has been returned private: heap h; };

#include "priority_queue.template"

#endif // _PRIORITY_QUEUE_H

Using the above heap header and queue header, I need to construct a priority queue using a vector as opposed to a dynamic array. This is based off of question 2 in chapter 11 in Data Structures and Other Objects Using C++