如何从priority_queue中删除不在顶部的元素？

Question

在我的程序中,我需要从不在顶部的优先级队列中删除一个元素.可以这样做吗？如果没有,请建议一种方法,除了创建自己的堆.

Answer 1

标准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()) {
            this->c.erase(it);
            std::make_heap(this->c.begin(), this->c.end(), this->comp);
            return true;
       }
       else {
        return false;
       }
 }
};

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

Answer 2

最好的解决方案是使用 std::set。Sets 提供了允许它同时用作最小/最大堆（或优先级队列）的方法。

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);

Answer 3

处理priority_queue STL 删除的一个巧妙的小技巧——使用另一个priority_queue，例如，del_pq。继续插入所有删除值。当您从原始优先级队列中弹出值时，请检查 top ofdel_pq并查看我们是否要删除它。如果匹配，则从原始 priority_queue 中删除该值。

这个方法实现了一种懒惰地删除我们原始优先级队列中的值的方法。可以占用两倍的内存，但平均删除和插入保持不变O(logN)。

Answer 4

Pradip 和 MASh 牺牲了时间来实现删除操作。但是如果时间复杂度对你很重要，我建议你使用 hash min_heap。哈希表存储值指针，指针指向 min_heap。这意味着您可以花费 O(1) 时间来查找 min_heap 和 O(log(n)) 中的值以删除（向上或向下筛选）元素。

Answer 5

请注意 ，以下方法可以完成任务，但不是解决问题的优化方法。对于优化方法，请检查其他答案。

让你想要删除 中的第 5 个元素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);
}