如何配置std::priority_queue以忽略重复项？

Question

我如何配置 std::priority_queue 以忽略重复项？

当我添加一个已经存在的键时，应该忽略这个新键。(在我的情况下，旧键和新键的优先级总是完全相同的。)

就复杂度而言，这不会有任何影响：它将尝试在适当的位置插入，找到已存在的键并什么都不做。问题只是是否可以通过配置来实现这一点，std::priority_queue 是否支持这种方式。

- Frank

---

我认为堆不支持在O(log N)时间内“查找现有元素”。 - kennytm

@KennyTM，幸运的是，pqueue不一定要是堆;-) - ltjax

@KennyTM：为了找到现有的（注意：与新的具有相同的优先级），我们首先在O(log N)时间内找到插入位置，然后在该位置上识别现有的键（在O(log N)中进行二进制搜索）。我错过了什么吗？ - Frank

你忽略了一个事实，即std::priority_queue很可能是作为最大堆二叉树来实现的，它没有固定的“适当插入位置”来存储任何值。新值被插入到末尾，然后向上过滤到其所有子节点具有较低值的第一个位置。具有相同优先级的多个键的插入可能会最终落在完全不同的树枝中。 - AShelly

Answer 1

你可以通过STL set实现优先队列。

在C++中实现可迭代的优先队列

- Aater Suleman

Answer 2

如Aater所提到的，您可以使用stl set作为优先队列。

另一个选择是将重复项添加到优先队列中，但在弹出队列中的项目时，要跟踪先前的值并忽略重复的值。例如，这里是处理所有值的优先队列，同时忽略重复项。

    priority_queue<int> pq = /* values */;
    
    int curr = 0;
    int prev = 0;
    bool first = true;
    while(isplit < target) {
        prev = curr;
        curr = pq.top();
        pq.pop();
        if (!first && prev == curr) {
            continue;
        }
        first = false;
        // do something with curr
    }

- tfinniga