随机访问优先队列

Question

继续列表到优先级队列

我正在实现一个具有随机访问功能的改进的priority_queue。

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_;
};

我走的路正确吗？

• 修复了一元构造函数。
• 改进的代码。

Answer 1

对我来说看起来不太好：

• 一元构造函数应该通过 const 引用获取参数。
• 赋值运算符不检查自赋值。
• getContainer() 方法显示接口缺乏清晰度 - 为什么要简单地公开这样的实现细节？
• 最重要的是：为什么需要“随机访问优先级队列”？

Answer 2

您的 pop() 方法可能会违反堆顺序。使用 pop_heap() 而不是 pop_back()。我现在似乎找不到任何其他错误。

您可以通过推入随机整数并逐个 pop() 来轻松测试此类实现。您应该按排序顺序将它们取回。这称为堆排序。

建议：

• 您可以为此类实现一个 const 迭代器，而不是返回对容器的引用。

• 请注意，不应更改随机访问元素的键，因为这可能会破坏堆结构。如果您需要这样的功能，您应该实现一个change_key函数，它将安全地更改密钥并维护堆排序。