PriorityQueue changes order when removing an element

user_14459522 0
Viewed 521

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.

priority-queue data-structures java
2 Answers

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.

user_15535370

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