这是错误的代码:
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;
};