CODEWITHSUNDEEP
javapriority-queue
Yahya Uddin
Yahya Uddin

Reputation: 28861

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

In java, I want to decrement the value of each element in a priority queue by 1.

This is a sample of some code of what I tried:

// more code

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

// code that adds items to q

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

However it does not seem to change the priority queue items at all. How do I fix this code so it does what I intended?

Thanks!

Upvotes: 0

Views: 2705

Answers (5)

kpentchev
kpentchev

Reputation: 3090

First you need to understand why it doesn't change the value of item. The reason is that Integer is an immutable class, meaning that once the class instance is assigned a value (int) it won't change. You can modify your loop statement to create a new Integer that has the decremented value or use the AtomicInteger class and its getAndDecrement method. The latter however has some synchronization overhead.

Update with code samples

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

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

Upvotes: 3

Ivan Matavulj
Ivan Matavulj

Reputation: 145

You can simply create another queue and populate it by adding decremented values from the first one:

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);
}

Upvotes: 2

Alexander R.
Alexander R.

Reputation: 1756

You must understand how PriorityQueue works.

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.

You cant't to increase priority in way you are using PriorityQueue. You only can change the priority by re-ordering elements in q.

Now, if you really want to have priorities as property of any object, you must define your own wrapper to object. For examlpe:

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;
    }
}

And use it as 

   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);
    }

Now you can loop over queue and change priority to your items:

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

Upvotes: 0

DominikAngerer
DominikAngerer

Reputation: 6530

I would create a new PriorityQueue<Integer> and iterate over the first one like this:

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

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

As you can see we iterate over the PriorityQueue<Integer> simply using an Iterator and after you are done with your processing simply set the newQueue to your old variable or do all of that in a method and return your newQueue.

Upvotes: 2

Brett Okken
Brett Okken

Reputation: 6306

Mutating objects within a PriorityQueue is likely to lead to inconsistent behavior. While the javadoc does not state this explicitly, it is hinted at by the fact that inserting elements is a O(log(n)) operation but getting the top of the queue (peek or element) without actually removing is constant time:

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).

This seems to indicate that the elements are sorted at addition and expected to remain in that same sort order. Mutating objects within the queue in a way that impacts the comparison does not appear to be accounted for.

Upvotes: 2

Related Questions