如何从按值排序的Pair类型PriorityQueue中按key删除指定元素

问题场景 #

给定按Pair的value升序排序的PriorityQueue：

PriorityQueue<Pair<Integer, Integer>> p = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
p.add(new Pair<>(2,1));
p.add(new Pair<>(3,4));
p.add(new Pair<>(1,5));

需要删除key为3的元素(3,4)，最终队列应保留[[2,1], [1,5]]。

解决方案 #

Java的PriorityQueue基于堆结构实现，没有直接按key检索删除元素的API，以下两种方法均可实现需求：

方法1：临时集合过滤后重建队列

将队列元素全部取出，过滤掉目标元素后重新加入原队列：

// 存储需要保留的元素
List<Pair<Integer, Integer>> temp = new ArrayList<>();
while (!p.isEmpty()) {
    Pair<Integer, Integer> elem = p.poll();
    if (!elem.getKey().equals(3)) {
        temp.add(elem);
    }
}
// 清空原队列并重新添加过滤后的元素
p.clear();
p.addAll(temp);

方法2：迭代器遍历删除

利用迭代器安全遍历队列，找到目标key的元素后直接删除：

Iterator<Pair<Integer, Integer>> iter = p.iterator();
while (iter.hasNext()) {
    Pair<Integer, Integer> elem = iter.next();
    if (elem.getKey().equals(3)) {
        iter.remove();
        break; // 若需删除所有key为3的元素，移除该行即可
    }
}

说明 #

• 方法1适合批量过滤元素的场景，会重新构建堆结构，保证队列的排序特性不受影响。
• 方法2更高效（无需全量取出元素），需注意：PriorityQueue的迭代器遍历顺序并非堆的排序顺序，但不影响元素的删除操作。

内容的提问来源于stack exchange，提问作者Rahul Rasve