Random Access Priority Queue

Question

Continued Priority Queue List

I am implementing an improved priority_queue with random access.

template <class T, class Container = std::vector<T> > class Heap { public: Heap() {} Heap(const Container& container) { container_ = container; std::make_heap(container_.begin(), container_.end()); } Heap<T, Container>& operator=(const Heap<T, Container>& heap) { if (this != &heap) container_ = heap.container_; return *this; } void push(const T& x) { container_.push_back(x); std::push_heap(container_.begin(), container_.end()); } void pop() { std::pop_heap(container_.begin(), container_.end()); container_.pop_back(); } const T& top() { return container_.front(); } const Container& getContainer() const { return container_; } T& operator[](size_t n) { return container_[n]; } typename Container::const_iterator begin() const { return container_.begin(); } typename Container::const_iterator end() const { return container_.end(); } size_t size() const { return container_.size(); } T& base() { return container_.back(); } Container::iterator erase(Container::iterator position) { return container_.erase(position); } private: Container container_; }; 

Am I taking the right paths?

• Unary constructor fixed.
• Improved code.

Answer 1

Doesn't look so great to me:

• The unary constructor must accept an argument using the const reference.
• The assignment operator does not check self-determination.
• The getContainer() method shows a lack of clarity in the interface - why would you just expose implementation details this way?
• Most importantly: why do you need a "random access priority queue"?

Answer 2

Your pop () method may break the heap order. Use pop_heap () instead of pop_back (). I do not seem to see any other error.

You can easily test such an implementation by pressing random integers and pop () them one at a time. You must return them in sorted order. This is known as heap sorting.

Suggestions:

• Instead of returning ref to the container, you can implement a constant iterator of this class.

• Note that you should not change the key of a random access element, as it can destroy the heap structure. If you need such functionality, you must implement the change_key function, which will safely change the key and maintain heap order.