java - 如何让优先级队列自行重新排序

Question

我有一个优先级队列，用于跟踪员工列表，并且它用于在开始时对它们进行排序的比较器按当前的“邀请值”对它们进行排序。所以我想选择最大邀请值员工，邀请他，然后重新选择下一个最大邀请值员工。棘手的部分是，在我邀请某个员工后，它会影响列表中其他一些员工的邀请值。我尝试过以下方法

PriorityQueue<Employee> leafs = new PriorityQueue<>();
//populating the queue happens here

while(!leafs.isEmpty()){

Employee maxLeaf = leafs.peek();
        int maxValue = maxLeaf.getInviteValue();

        maxLeaf.invite();
        totalValue += maxValue;
        k--;

        for(Employee e : leafs){
            if(e.invValueChanged){
                leafs.remove(e);
                leafs.add(e);
            }
        }
}

每位员工都会通过查看其 invValueChanged 字段来了解是否需要根据上次邀请重新计算其值(value)。这段代码给我一个优先队列错误

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.PriorityQueue$Itr.next(PriorityQueue.java:535)

Answer 1

这里的问题是，您需要更改数据结构中的其他元素。

您不能只迭代它们并对它们进行操作，这将改变元素的顺序。

做到这一点的最佳方法是创建当前结构的 vector ，对 vector 进行操作，然后重新插入它们。

如果速度让您烦恼，那么此操作的时间复杂度与您编写的代码相同。

在优先级队列中插入一个元素需要 O(log(n)) 时间，您执行了 n 次，因此您获得了 O(n log (n)) 时间。

从优先队列创建 vector 需要 O(n) 时间。从 vector 中插入优先级队列中的所有元素需要 O(n log(n)) 时间。

所以速度应该是渐近相同的。真实速度应该也很接近。