可删堆的死循环问题
优先队列能够将一组数的极值放在最前面。但是它本身不能像平衡树那样随便删除中间的元素(当然直接用 set
也行)。
我们可以使用两个优先队列,一个用来存储原数据(记作 que
),另一个用来存储要删除的元素(记作 del
)。每当想要访问 que.top()
时,都先执行一个 while
循环,若 que.top() == del.top()
,就把两个队列的队首都弹出。
然而如果 del
中存在一个 que
中已经删除的元素,并且这个元素还比 que
中最大的元素都大,程序就会卡在 while
循环外面,不能正常删除。
因此我们在 while
循环上添加一个特判:如果 del.top() >= que.top()
,就只执行 del.pop()
。这样即使把 que
中已经删除的元素 push
进了 del
,程序也能正常运行。