C++ 如何从priority_queue中删除不在顶部的元素？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19467485/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to remove element not at top from priority_queue?
提问by ishan3243
In my program I need to delete an element from a priority queue that is not at the top. Can that be done? If not, please suggest a way to do so except creating your own heap.
在我的程序中，我需要从不在顶部的优先级队列中删除一个元素。可以做到吗？如果没有，请提出一种除创建自己的堆之外的方法。
回答by alexm
The standard priority_queue<T>can be customized through inheritance. It has protected members cand compthat can be referenced in a descendant class.
标准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 << ", ";
}
}
}
Output:
输出：
10, 4, 3, 2
10, 4, 3, 2
回答by Amit Kumar
The best solution is to use std::set. Sets provide methods which allow it to be used both as a min/max heap (or a priority queue).
最好的解决方案是使用 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();
Furthermore sets also allow random deletion.
此外，集合还允许随机删除。
//to delete the integer '6'
auto it = pq.find(6);
pq.erase(it);
回答by Y. Xu
Pradip and MASh sacrifice the time to realize the remove operation. But if time complexity is important to you, I suggest you to use hash min_heap. A Hash table stores the value-pointer and the pointers point to a min_heap. Which means you can spend O(1) time to find the value in min_heap and O(log(n)) to remove(sift-up or sift down) the element.
Pradip 和 MASh 牺牲了时间来实现删除操作。但是如果时间复杂度对你很重要，我建议你使用 hash min_heap。哈希表存储值指针，指针指向 min_heap。这意味着您可以花费 O(1) 时间来查找 min_heap 和 O(log(n)) 中的值来删除（向上或向下筛选）元素。
回答by Rishabh Jain
A neat little trick to handle deletes for a priority_queue STL - use another priority_queue, say, del_pq. Keep inserting all the delete values to this. When you are popping values from the original priority queue, check with top of del_pqand see if we wanted to delete it. If it matches, delete the value from the original priority_queue.
处理priority_queue STL 删除的一个巧妙的小技巧——使用另一个priority_queue，例如，del_pq。继续插入所有删除值。当您从原始优先级队列中弹出值时，请检查 top ofdel_pq并查看我们是否要删除它。如果匹配，则从原始 priority_queue 中删除该值。
This method implements a way to lazily delete the values in our original priority queue. Can take up twice the memory, but average delete and inserts remain O(logN).
这个方法实现了一种懒惰地删除我们原始优先级队列中的值的方法。可以占用两倍的内存，但平均删除和插入保持不变O(logN)。
回答by MASh
Let you want to delete the 5th element in the priority_queue<type> Q.
Then you can do this like:
让您想要删除priority_queue<type> Q. 然后你可以这样做：
vector<type> tempQ;
int i=0;
int n=5;
type t;
while(i<n-1)
{
tempQ.push_back(Q.top());
Q.pop();
i++;
}
Q.pop();
i=0;
while(i<n-1)
{
t=tempQ[i++];
Q.push(t);
}
