Problem 2:The Priority Queue ADT is a data structure that allows access to the smallest (highest priority) data item at cheap cost O(1), and insertion and removal of data items are always of cost O(log N) (N = size of data set). The PriorityQueue member functions are push (insert a data time), pop (remove the smallest item), and top (access the smallest item). Provide the C++ implementations of these member functions when the data items are stored in a private data member of type BinaryHeap.

template

class PriorityQueue

{

public:

PriorityQueue() {}

PriorityQueue(const PriorityQueue& rhs)

: theheap{rhs.theheap}, theSize{rhs.theSize} {}

const C & top() const;

void push(const C & x);

void pop()

private int theSize;

BinaryHeap theheap;

};

template

const C & PriorityQueue?top() const

{

// fill in code

}

template

void Prioirty?push(const C & x)

{

// fill in code

}

template

void PriorityQueue?pop()

{

// fill in code

}

Continue on next page

You may assume the following definition for class BinaryHeap, and you must use only functions from the interface of class BinaryHea to implement the PriorityQueue functions.

template

class BinaryHeap

{

public: BinaryHeap();

BinaryHeap(const Vector&);

bool isEmpty() const;

int size() cont;

const C & findMin() const;

void insert(const C &);

void insert(C &&);

void deleteMin();

void deleteMin(C &);

void makeEmpty()

private: int currentSize;

Vector heap;

void buildHeap() void percolateDown(int);

};