Search code examples
javapriority-queue

Offering more elements to a Priority Queue?

I was wondering why the output for the following is [12, 15, 12]? I know that Priority Queue sorts its elements through heaps, but how come 12 is not put before the 15? Thank you so much! :)

Queue<Integer> q;
q= new PriorityQueue<>();
q.offer(15);
q.offer(12);
q.offer(2);
q.poll();
q.offer(q.peek());
q.peek();
System.out.println(q);
Solution

  • You should get in the habit of consulting the Javadoc for JDK classes.

    System.out.println(q), according to its documentation, calls String.valueOf(q), which according to its documentation calls q.toString(), which according to its documentation uses the order of elements from q.iterator(), which according to its documentation is not in any particular order.

    If you think about how priority-queues are implemented (typically as some sort of heap structure), this makes sense: a heap doesn't keep track of the order of elements, other than to ensure that each node has a lesser value than all of its descendant nodes. To return the elements in a meaningful order would require worst-case O(n log n) time.