如何在 Java 中迭代和更改优先级队列中每个项目的值

Question

在java中，我想将优先级队列中每个元素的值减1。

这是我尝试过的一些代码示例：

// more code

PriorityQueue<Integer> q = new PriorityQueue<Integer>(size, Collections.reverseOrder());

// code that adds items to q

for (Integer item: q) {
   item--;
}

但是它似乎根本没有改变优先级队列项目。我该如何修复此代码，使其按照我的预期运行？

谢谢！

Answer 1

首先你要明白为什么它不改变item的值。原因是 Integer 是一个 immutable class，这意味着一旦 class 实例被分配了一个值（int）它就不会改变.您可以修改循环语句以创建具有递减值的新 Integer 或使用 AtomicInteger class 及其 getAndDecrement 方法。然而后者有一些同步开销。

更新代码示例

PriorityQueue<AtomicInteger> q = new PriorityQueue<AtomicInteger>(size,  Collections.reverseOrder());

// code that adds items to q
for (AtomicInteger item: q) {
   item.getAndDecrement();
}

Answer 2

我会创建一个新的 PriorityQueue<Integer> 并像这样迭代第一个：

Queue<Integer> newQueue = new PriorityQueue<Integer>(); 

Iterator<Integer> itr = q.iterator();
while(itr.hasNext()){
    Integer current = q.poll();
    // do some processing with current
}

如您所见，我们仅使用 Iterator 迭代 PriorityQueue<Integer>，完成处理后，只需将 newQueue 设置为旧变量或执行所有操作在一个方法中 return 你的 newQueue.

Answer 3

改变 PriorityQueue 中的对象可能会导致不一致的行为。虽然 javadoc 没有明确说明这一点，但插入元素是一个 O(log(n)) 操作但在不实际移除的情况下获取队列顶部（查看或元素）这一事实暗示了这一点时间：

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

这似乎表明元素在添加时已排序，并预计将保持相同的排序顺序。以影响比较的方式改变队列中的对象似乎没有被考虑在内。

Answer 4

您必须了解 PriorityQueue 的工作原理。

public PriorityQueue(int initialCapacity,
             Comparator<? super E> comparator)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

您不能以使用 PriorityQueue 的方式增加优先级。您只能通过重新排序 q.

中的元素来更改优先级

现在，如果您真的想将任何对象的优先级设置为属性，则必须为对象定义自己的包装器。例如：

public class PriorityItem implements Comparable<PriorityItem> {

    private int priority;

    public PriorityItem() {
        this.priority = 0;
    }

    public PriorityItem(int priority) {
        super();
        this.priority = priority;
    }

    public int getPriority() {
        return priority;
    }

    public void setPriority(int priority) {
        this.priority = priority;
    }

    @Override
    public int compareTo(PriorityItem obj) {
        // TODO Auto-generated method stub
        return this.priority-obj.priority;
    }
}

并将其用作

   PriorityQueue<PriorityItem > q = new PriorityQueue<PriorityItem >(20, new Comparator<PriorityItem>() {

    @Override
    public int compare(PriorityItem one, PriorityItem two) {
        // TODO Auto-generated method stub
        return one.compareTo(two);
    }

现在您可以遍历队列并更改项目的优先级：

for (PriorityItem item: q) {
   item.setPriority(item.getPriority() + 1);
}

Answer 5

您可以简单地创建另一个队列并通过添加第一个队列的递减值来填充它：

PriorityQueue<Integer> q = new PriorityQueue<Integer>(size, Collections.reverseOrder());
PriorityQueue<Integer> q2 = new PriorityQueue<Integer>(size, Collections.reverseOrder());

// code that adds items to q

for (Integer item: q) {
   q2.add(--item);
}

如何在 Java 中迭代和更改优先级队列中每个项目的值

How to iterate and change the value of each item in a priority queue in Java

java

priority-queue