Random access priority queue

问题:

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.

回答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"?

回答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.