Search code examples
javapriority-queue

Maximum priority queue functions

I define a maximum priority queue as below:

    PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

    queue.add(25);
    queue.add(3);
    queue.add(1);
    queue.add(3);
    queue.add(4);

I need to understand how this works especially when does the 1 gets the index of 2 only (not 4)?

Thanks.

enter image description here

Solution

  • It has no guaranteed order (https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html):

    The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

    Normally you retrieve elements according to their natural order using the poll() method, for example:

     while (!queue.isEmpty()) {
     var element = queue.poll();
     ...
 }

    EDIT:

    If you want to look at the internals of the class, this part of the code may be relevant (it basically uses a heap data structure):

    /**
 * Priority queue represented as a balanced binary heap: the two
 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
 * priority queue is ordered by comparator, or by the elements'
 * natural ordering, if comparator is null: For each node n in the
 * heap and each descendant d of n, n <= d.  The element with the
 * lowest value is in queue[0], assuming the queue is nonempty.
 */
transient Object[] queue;