The order of the PriorityQueue is wrong

user_7651355 0
Viewed 2324

I meet a problem about order of PriorityQueue in Java 8, Intellij Idea, when I add the third number in the queue, the order is wrong, but only the third one have this problem, here is my code.

import java.util.*;

public class vector {
    static Queue<Integer> q=new PriorityQueue<Integer>();
    public static void addNum(int num) {
        q.add(num);
    }
    public static void main(String args[]) {
        addNum(-1);
        addNum(-2);
        addNum(-3);
        addNum(-4);
        addNum(-5);
    }
}

I try to debug the code, after addNum(-3), the queue is -3,-1,-2, but after addNum(-4), the queue is -4, -3, -2, -1.

priority-queue java
4 Answers

The contract for PriorityQueue does not guarantee iteration order, but rather it guarantees that each element removed from the priority queue will follow either the natural ordering of the queue's type, or the ordering of a custom comparator, should one be provided.

The Javadoc comments on what you are seeing:

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out).

The contract which Java appears to enforce for priority queues is that the first element removed from the queue will follow the natural order of the object in the queue, or using a custom comparator, should one be provided.

If we add to your current script to remove the five elements added, we will see that the items returned will be ordered from least to greatest:

public static void main(String args[]) {
    addNum(-1);
    addNum(-2);
    addNum(-3);
    addNum(-4);
    addNum(-5);

    // now remove all elements
    while (!q.isEmpty()) {
        System.out.println(q.remove());
    }
}

This prints:

-5
-4
-3
-2
-1

If you need a collection which maintains sorting order, then consider using something like TreeSet. Or, you could use a regular ArrayList, and then call Collections.sort() if you want to impose a certain order.

user_18632290

PriorityQueue's implementation is a priority heap implementation & not sorted list.

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any specific order. If you need ordered traversal, use something like: 

Arrays.sort(q.toArray());
for (Integer data :q) {
  System.out.println(data);
}
user_77463980

As other answers implied, you should use queue.poll() if you want to retrieve the elements in the right order, as in:

    List<E> entities = new ArrayList<>();
    while(!queue.isEmpty()){
        entities.add(queue.poll());
    }

The order of entities in the entities list will be as expected.

Rationale: Java PriorityQueue only ensures the order of enqueuing of the entities, not the order of iteration in an underlying collection.

The entities are mapped onto an underlying collection "unsorted", meaning if you try to access the entities using a stream:

queue.stream().collect(Collectors.toList());

or an iterator:

Iterator<E> i = queue.iterator();
...
E e = i.next()

or any other method, such as queue.forEach(), or in fact observe your queue in a IDE debugger, there is no guarantee as to the order of the entries in the collections obtained using any of these methods.

user_57780990

This the most Common Question, Many Collection Frame Work like ArrayList, LinkedList, and furthermore but In PriorityQueue, when you are printing the elements it will be in the Sorted Order and that order is followed MIN_HEAP property or Basically, we can say that the Priority Queue is implemented on Min Heap Property. So First Understand the MinHeap then implement the code.

user_159054810
Related