求助,我的可删堆哪里写错了
  • 板块学术版
  • 楼主raincity
  • 当前回复14
  • 已保存回复14
  • 发布时间2023/12/2 17:08
  • 上次更新2023/12/2 20:12:59
查看原帖
求助,我的可删堆哪里写错了
253946
raincity楼主2023/12/2 17:08

这是错误的代码:

template <typename T>
class Heap {
public:
    void insert(const T& x)
    {
        ins.emplace(x);
    }

    void remove(const T& x)
    {
        del.emplace(x);
    }

    auto extract()
    {
        while (!del.empty() && ins.top() == del.top())
            ins.pop(), del.pop();
        auto x = ins.top();
        ins.pop();
        return x;
    }

private:
    std::priority_queue<T> ins, del;
};

这是正确的代码(使用 set 实现):

template <typename T>
class Heap {
public:
    void insert(const T& x)
    {
        s.emplace(x);
    }

    void remove(const T& x)
    {
        s.erase(x);
    }

    auto extract()
    {
        auto x = *std::prev(s.end());
        s.erase(x);
        return x;
    }

private:
    std::set<T> s;
};
2023/12/2 17:08
加载中...