java - PriorityQueue changes order when removing an element

Question

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.

question from:https://stackoverflow.com/questions/65847306/priorityqueue-changes-order-when-removing-an-element

Answer 1

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:

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 i^th 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.