如何从priority_queue中删除非顶部元素？

Question

如何从priority_queue中删除非顶部元素？

c++stlpriority-queuebinary-heap

64

在我的程序中，我需要从一个优先队列中删除一个不在顶部的元素。这可以做到吗？如果不能，请提供一种方法来实现，除了创建自己的堆之外。

- ishan3243

9

如果优先队列不支持你需要的操作，为什么你还要特别选择它？为什么不选择一个支持这些操作的数据结构，比如集合呢？ - Benjamin Lindley

9

哪些行为？快速访问最大（或最小）元素？set可以做到。快速删除任意元素？set也可以做到。 - Benjamin Lindley

13

那么请使用一个multiset。 - Benjamin Lindley

5

*mySet.begin()和*mySet.rbegin()的翻译如下：由于set是有序的，所以第一个和最后一个元素分别为最小和最大。 - Igor Tandetnik

2

可能是 STL 优先队列 - 删除项的重复问题。 - user1937198

显示剩余8条评论

5个回答

48

最佳解决方案是使用std::set。集合提供了方法，使其既可以用作最小/最大堆（或优先队列）。

std::set<int> pq;

//accessing the smallest element(use as min heap)
*pq.begin();

//accessing the largest element (use as max heap)
*pq.rbegin();

此外，集合还允许随机删除。

//to delete the integer '6'
auto it = pq.find(6);
pq.erase(it);

- Amit Kumar

12

如果元素可以重复，这种解决方案将行不通。 - Vipul Jain

7

我认为这个想法很酷，你可以使用 multiset 存储重复元素。但当你通过值而不是迭代器进行删除时，请记得注意。 - Po-Jen Lai

4

对于重复元素，你可以简单地使用一个map。只需要计算每个键的数量，当某个键的数量变为0时，将其移除。使用相同的思路解决了这个问题 https://www.spoj.com/problems/ARRAYSUB/。 - Yasser Hussain

1

@VipulJain 你可以使用多重集合。 - Tobias Wilfert

14

使用另一个优先队列del_pq是处理STL的优先队列删除的一个巧妙小技巧。将所有要删除的值插入其中。当从原始优先队列中弹出值时，请检查del_pq的最高优先级是否与我们想要删除的相匹配。如果匹配，则从原始优先队列中删除该值。

此方法实现了一种延迟删除原始优先队列中的值的方式。可能会占用两倍内存，但平均删除和插入仍为O(logN)。

- Rishabh Jain

我不确定顶部的元素是否总是答案，但使用unordered_set（或类似工具）进行删除也可以在次线性时间内完成。 - Ferazhu

5

Pradip和MASh花费时间实现了删除操作。
但是，如果时间复杂度对您很重要，我建议您使用哈希最小堆。
哈希表存储值指针，指针指向一个最小堆。
这意味着您可以在最小堆中花费O(1)的时间找到值，并在O(log(n))的时间内删除（通过sift-up或sift down）元素。

- Y. Xu

3

永远不要牺牲时间。 - Jon Deaton

-4

请注意，以下方法可以解决问题，但不是最优化的解决方案。如需最优化的解决方案，请查看其他答案。

假设您想要删除 priority_queue<type> Q 中的第五个元素。那么您可以这样做：

vector<type> tempQ;
int i = 0;
int n = 5;
type t;

// backup n-1 items
while(i < n-1)
{
    tempQ.push_back(Q.top());
    Q.pop();        
    i++;
}

// remove the nth item
Q.pop();

// restore the backed up items
i = 0;
while(i < n-1)
{
    t = tempQ[i++];
    Q.push(t);
}

- Shafi

1

那么这个方法的复杂度是什么？我不明白为什么需要使用临时 PQ。为什么不使用向量 vector<type> tempQ 呢？ - kevin

好的，这里我们只需要一个容器。使用向量代替将会提高时间复杂度。我已经更新了答案。感谢你的建议 @kevin，给你点赞。 - Shafi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- alexm · Accepted Answer

通过继承，可以自定义标准的priority_queue<T>。后代类可以引用它的受保护成员c和comp。

template<typename T>
class custom_priority_queue : public std::priority_queue<T, std::vector<T>>
{
  public:

      bool remove(const T& value) {
          auto it = std::find(this->c.begin(), this->c.end(), value);
       
          if (it == this->c.end()) {
              return false;
          }
          if (it == this->c.begin()) {
              // deque the top element
              this->pop();
          }    
          else {
              // remove element and re-heap
              this->c.erase(it);
              std::make_heap(this->c.begin(), this->c.end(), this->comp);
         }
         return true;
     }
};

void main()
{
   custom_priority_queue<int> queue;

   queue.push(10);
   queue.push(2);
   queue.push(4);
   queue.push(6);
   queue.push(3);

   queue.remove(6);

   while (!queue.empty())
   {
      std::cout << queue.top();
      queue.pop();

      if (!queue.empty())
      {
        std::cout << ", ";
      }
   }

 }

输出：

10、4、3、2