Problem 2:The Priority Queue ADT is a data structure that allows access to the s

Question

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 <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 …

}

template <typename C>

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

{

// fill in code …

}

template <typename>

void PriorityQueue<C>?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 <typename C>

class BinaryHeap

{

public: BinaryHeap();

BinaryHeap(const Vector<C>&);

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

void buildHeap() void percolateDown(int);

};

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.