优先队列中的删除

Question

我有一个代码 (Andorid)，它遍历优先级队列并删除具有特定 ID 的所有条目。

但是，它只删除第一个实例并跳过其余实例。例如，

(abc 1) （定义 2） (ghi 3) (jkl 1) (mno 3)

如果给定的 id 是 1。它只会删除 abc 并且队列会重新组织并在其中留下 jkl。我也厌倦了迭代器，但没有用。

for(SomeMessage message : priorityQueue){

          if(message.id == dead_sender.id){
                      priorityQueue.remove(message)
       }

}

Answer 1

您不能在 for-each 循环中迭代集合并同时删除其中的元素。

您应该在迭代时为 "items to remove" 创建一个单独的集合。完成后，迭代这个新集合，从原始集合中删除每个项目。

类似于：

List<SomeMessage> toRemove = new ArrayList<>();
for(SomeMessage message : priorityQueue){

          if(message.id == dead_sender.id){
                      toRemove.add(message);
       }
}
for (SomeMessage message : toRemove) { 
      priorityQueue.remove(message)
}

但是请注意，删除优先级队列的任意元素（不是头部）是一项昂贵的任务 (O(n))，如果这成为一个问题，您可能需要将设计更改为：

使用TreeSet或完全有序的数据结构
不是标记要删除的项目，而是标记要保留的项目 - 而不是删除它们 - 使用这些项目构建一个新的 PriorityQueue。

优先队列中的删除

Deletion in Priority Queue

java

android

data-structures