Random access priority queue

Question

Continuing List to priority queue

I'm implementing a 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 way?

• Fixed the unary constructor.
• Improved code.

Disputatious

If it's random access, it's no longer a priority queue. – Savino

It's supposed to behave like a priority_queue but with the possibility of random access. – Disputatious

Answer 1

Doesn't look that great to me:

• The unary constructor should take argument by const reference.
• The assignment operator doesn't check for self-assignment.
• The getContainer() method shows a lack of clarity in the interface - why would you simply expose the implementation detail like that?
• Most importantly: why do you want a "random access priority queue"?

Rotgut

I've fixed the unary constructor. I don't understand your second statement and I'm gonna fix the third point. About your question, it's for a college project that, as you can see, is badly structed. – Disputatious

Thanks for the great link. I updated my code. Is it better? Sorry for the inconvenience but it's the first time I do something like this. – Disputatious

one possible reason to want this is to iterate through the queue's elements (i.e. peek at further contents). I always find std::stack<> to be particularly painful as it doesn't allow you to examine it's contents. I always switch back to using the underlying vector directly. – Sclaff

Answer 2

Your pop() method can violate the heap ordering. Use pop_heap() instead of pop_back(). I can't seem to find any other bug right now.

You can easily test such an implementation by pushing in a random integers and pop() them one by one. You should get them back in sorted order. This is known as heap sort.

Suggestions:

• Instead of returning a ref to the container you could implement an const iterator to this class.

• Note that you should not change the key of the randomly accessed element because it may destroy the heap structure. If you need such functionality you should implement a change_key function which would change the key safely and maintain the heap ordering.

Handicapper

@Renato: your begin() and end() methods return Container::iterator. They should always return Container::const_iterator or someone can (read: will) mess up your heap. – Sclaff

@André: Thanks! I changed the methods. Anything else that I should improve? – Disputatious