5

Without providing custom comparator the priority queue inserts elements in ascending order, however, after removing a particular element the order is changed.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(1);
pq.add(2);
pq.add(2);
    
pq.remove(2);
for(int x: pq) {
    System.out.println(x);
}

//outputs: 1 10 2, instead of expected: 1 2 10

Any ideas?

Thanks.

2
  • To add on, the actual storage array backing PriorityQueue is essentially a heap/tree structure. Iterating that array (which is how the enhanced for-each evaluates here) will iterate the elements in order of their storage, not of how they're traversed over the heap. So to the average person, it's essentially an "unordered" array. But that does not mean the queue-related methods (like #poll, see below) are unordered.
    – Rogue
    Commented Jan 22, 2021 at 14:54
  • The answer to this is right in the javadoc for PriorityQueue: "The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order."
    – jtahlborn
    Commented Jan 22, 2021 at 17:40

2 Answers 2

4

Don't iterate on your PriorityQueue<T> as you do on a collections/arrays; use .poll(), instead:

while(pq.peek()!=null) {
    System.out.println(pq.poll());
}

Priority Queue is an Abstract Data Type, that is often implemented as a Binary Heap data structure, which, in turn, is (commonly) implemented with the array. There are some other ways to implement binary heap, but an ordinary array, is the fastest, simplest and best way for it.

An example of how the array represents a binary heap, looks like this:

enter image description here

Queue order is not being changed, in your case; rather, you're just utilizing data structure in a wrong way, by merely iterating on it in a traditional for-each/iterative way, as when you iterate on a basic array, not considering, that your Priority Queue backing array is not sorted with its ith index; rather it maintains the top element on top of tree (either Min Heap or Max Heap case) and you can't just get the .poll() effect by iterating on it in a traditional way.

9
  • Interesting. Even using iterator it shows it as 1 10 2, any reason why the difference in output with .poll()? Commented Jan 22, 2021 at 14:53
  • See my comment to the question
    – Rogue
    Commented Jan 22, 2021 at 14:54
  • Thank you, that explains it! Commented Jan 22, 2021 at 15:05
  • Maybe move that comment into your answer?
    – Robert
    Commented Jan 22, 2021 at 15:52
  • This is a good explanation of the chosen implementation, but the real answer here is that the public documentation for PriorityQueue answers the question (regardless of the chosen implementation): "The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order."
    – jtahlborn
    Commented Jan 22, 2021 at 17:42
0

This is because PriorityQueue is an implementation of min heap (in Java by default), this means the root element will be always lower than the other elements in the list.

To take the example from your question:

  1. When you insert 10, in the array the element at index 1 is 10
  2. When you insert 1, as 1 < 10 the element at position 1 is now 1 and 10 it shifted to index 2
  3. When you insert 2, as 1 < 2 there is no need to shift the element, and 2 is inserted at index 3
  4. When you insert 2, the 2 will go under 10, as 10 > 2 a shift is needed, 2 is inserted at 2 and 10 is shited to the index 4

After all inserts the array looks like this, also check the video below:

array: [NULL, 1, 2, 2, 10]

enter image description here

Now when you remove 2, a shift is required for 10, and 10 is moved back to index 2, and the state of array is [NULL, 1, 10, 2] and this is what you see as the output when you iterate. Also, check the following method that is implemented inside PriorityQueue and is used when you don't provide a Comparator.

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.