Problem 2: (10 % of Final) The Priority Queue ADT is a data structure that allow

Question

Problem 2: (10 % of Final) 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 PriorityQueues rhs) : theheapirhs.theheap) thesizeirhs.theSize const c& top) const: void push ( const C x); void pop) private int theSize; BinaryHeap theheap template const C & PriorityQueuestop () const / fi1l in code template void Prioirtycc>push (const C&x;) / fill in code.. template void PriorityQueueccpop () / fill in code... Continue on next page

Explanation / Answer

template <typename C>

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<C> theheap;

};

template <typename C>

const C & PriorityQueue<C>?top() const

{

// fill in code …
// Heap always minimum element on top
// so access to it is always O(1)
return findMin();

}

template <typename C>

void Prioirty<C>?push(const C & x)

{

// fill in code …
// Heap always implements insert in O(n)
theheap.insert(c);

}

template <typename>

void PriorityQueue<C>?pop()

{

// fill in code …
// Heap always implements deleteMin in O(n)
theheap.deleteMin();
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.