CODEWITHSUNDEEP
javapriority-queue
Nilzone-
Nilzone-

Reputation: 2786

Retrieve item from the middle of a PriorityQueue in Java

Given the following code:

import java.util.*;

class SimpleTest {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(1);
        pq.add(2);
        pq.add(3);
        pq.add(4);
        pq.add(5);
        pq.add(6);
        pq.add(7);

        int index = 0;
        int middleNumber = 0;
        Iterator it = pq.iterator();

        //Is number odd
        if(pq.size() % 2 != 0) {
            System.out.println(pq.size());

            //keep removing from queue until we reached queueSize/2 (rounded up)
            while(it.hasNext() && index++ <= ((pq.size() >> 1) + 1)) {
                middleNumber = pq.poll();
            }
            System.out.println("The middle number is: " + (float)middleNumber);
        }       

    }
}

This works on some odd numbers, but not others, and I fail to see why.

Given a queue of 7 items, the code above returns 4 which is in the middle of the queue.

But If I try a queue with 9 elements (1-9). It also returns 4, when it should be 5.

Why does this happen?

Upvotes: 0

Views: 5078

Answers (2)

user207421
user207421

Reputation: 310985

The iterator of a PriorityQueue doesn't iterate in priority order, just in the natural order of the underlying collection. See the Javadoc.

The only way to get the priority order is by calling PriorityQueue.remove().

Upvotes: -1

ruakh
ruakh

Reputation: 183446

The main problem is that this line:

                middleNumber = pq.poll();

decrements the size of the queue, which affects the meaning of this line:

            while(it.hasNext() && index++ <= ((pq.size() >> 1) + 1)) {

Then there are secondary problems — the while expression is wrong as written — which I think is because you tried to tweak the while to work for the case where the queue started with 7 elements, not understanding the underlying bug.

Instead, you should precompute what index you want, and poll to that point:

int indexOfMiddleNumber = pq.size() / 2;
for (int index = 0; index < indexOfMiddleNumber; ++index) {
    pq.poll();
}
int middleNumber = pq.poll();

(Note that there's no use for the iterator, and it's actually a really bad idea to call it.hasNext() in a loop that's also modifying the underlying collection. I'm surprised that PriorityQueue isn't giving you a ConcurrentModificationException for this.)

Upvotes: 2

Related Questions