Goal is to do Problem 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). Implement problem 1 with NO PREDIFINED LIMIT ON THE SIZE OF THE HEAP USING A VECTOR

* Use the heap class to implement a priority queue *

----- Use the following header files ------

heap.h

#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_

priority_queue.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