CODEWITHSUNDEEP
javadata-structurespriority-queue
Ankit Singodia
Ankit Singodia

Reputation: 631

When are elements ordered in PriorityQueues?

Does the PriorityQueue class inserts the elements priority wise or it's just that when we poll the element only then it finds out the highest priority element and returns it?

Upvotes: 3

Views: 233

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 133975

As others have mentioned, the PriorityQueue classes internally maintains a binary heap, and the ordering of items in that heap is determined by either the default ordering, or by a Comparator. The binary heap is maintained in a list.

Your question asks when elements are ordered. When you add an item to the queue or remove an item from the queue, the order of items is rearranged so that the highest priority item is at the top of the heap: at index 0 in the list. So the answer to your main question is that PriorityQueue always knows which is the highest-priority item. That makes the peek() function very efficient.

The order of items in the rest of the list is a little more involved. The rest of the list is ordered, but not necessarily sorted. The ordering is such that rearranging the heap after insertion or removal is efficient. See the above-linked article on binary heaps for the details about heap ordering.

Upvotes: 1

Naman
Naman

Reputation: 31868

From the source code of JDK itself(formatting mine):

The 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 the comparator, or by the elements' natural ordering, if the 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 non-empty.

So, you can consider the insertion/deletion of elements in PriorityQueue as operations providing results along with the balancing of the heap.

Upvotes: 2

Related Questions