跳转至

可删堆的死循环问题

优先队列能够将一组数的极值放在最前面。但是它本身不能像平衡树那样随便删除中间的元素(当然直接用 set 也行)。

我们可以使用两个优先队列,一个用来存储原数据(记作 que ),另一个用来存储要删除的元素(记作 del)。每当想要访问 que.top() 时,都先执行一个 while 循环,若 que.top() == del.top(),就把两个队列的队首都弹出。

然而如果 del 中存在一个 que 中已经删除的元素,并且这个元素还比 que 中最大的元素都大,程序就会卡在 while 循环外面,不能正常删除。

因此我们在 while 循环上添加一个特判:如果 del.top() >= que.top(),就只执行 del.pop()。这样即使把 que 中已经删除的元素 push 进了 del,程序也能正常运行。