Search code examples
javadata-structurespriority-queue

PriorityQueue changes order when removing an element

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.

Solution

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