1. Introduction to PriorityQueue in Java

The corresponding array can be:

Notice that the array is not fully sorted. The heap only requires each parent to rank before or equal to its children. For example, 3 can appear before 8 in a sorted list while occupying a later array position in the heap. The ordering relationship between elements in separate branches is not a global sorted-order guarantee.

Array index relationships

For an element at index i in a zero-based heap array:

• Parent index: (i - 1) / 2, for a node other than the root.
• Left child index: 2 * i + 1.
• Right child index: 2 * i + 2.

These relationships allow the implementation to move through the conceptual tree using array indexes.

4. How Insertion Works: Offer and Bubble Up

When a new element is inserted, the implementation places it in the next available position at the end of the heap array. It then compares the new element with its parent.

If the new element should come before its parent, the two positions are exchanged. The process continues upward until the element is no longer ranked before its parent or it reaches the root. This operation is often called sift up, bubble up, or heapify up.

For example, suppose a min-heap contains 2, 5, 8, and the value 1 is inserted. The value is initially placed in the next array slot. Since 1 is smaller than its parent, it moves upward. It continues until it becomes the root.

Because the heap is balanced in shape, the path from a leaf to the root has logarithmic length. Inserting an element therefore takes \(O(\log n)\) time in the worst case, where n is the number of elements.

The internal arrangement can change during insertion. Code should depend on the documented ordering behavior of the head, not on a particular array layout.

5. How Removal Works: Poll and Sift Down

The head is the minimum element in a default min-heap. When poll() removes it, the implementation cannot leave a gap at the root.

The last element in the heap array is moved to the root, and the heap is repaired by moving that element downward. It is compared with its children and exchanged with the child that should come first. This continues until the heap property is restored.

This operation is often called sift down or heapify down.

The downward path is logarithmic in the heap size, so removing the head takes \(O(\log n)\) time. The exact internal swaps are implementation details; the guaranteed result is that poll() returns the current head according to the queue's ordering.

6. Core PriorityQueue Methods

The most frequently used methods come from the Queue and Collection interfaces.

These are typical documented performance characteristics. The complexity of offer() and poll() reflects maintaining the heap. contains() and remove(Object) are linear because a heap does not provide a direct path to an arbitrary value.

Understanding the main three methods

• offer(e) adds an element and returns true when insertion succeeds. It is generally preferred in queue-oriented code.
• peek() inspects the current head without changing the queue.
• poll() removes the current head and returns it.

For an empty queue, peek() and poll() return null. Since PriorityQueue does not allow null elements, this return value can reliably indicate that no head was available.

7. A Practical Example: Processing Order Priorities

Suppose a store assigns each order a numeric priority, where a lower number indicates a more urgent order. A PriorityQueue<Integer> can hold those priority values and return the lowest value first.

Output:

11
2
3

The repeated value 1 is allowed. A PriorityQueue is not a Set; it can contain duplicate elements. Both entries with priority 1 will be returned before priority 2.

In a real application, the queue would often contain task or order objects rather than just priority numbers. A comparator can specify how those objects should be ranked.

8. Why Iteration Does Not Produce Sorted Order

A common misconception is that every element in a PriorityQueue is stored in sorted order. That is not how a heap works.

The heap guarantees that the head has the highest rank under the configured ordering. It does not guarantee that the second element is the second-smallest overall, or that walking the backing array will produce a sorted sequence.

For example, the internal array for a valid min-heap might be:

 [1, 2, 8, 5, 3]

The first element is the minimum, but the complete array is not sorted. Iterating over the queue may therefore produce 1, 2, 8, 5, 3, or another valid heap-array order.

How to obtain sorted output

There are two common approaches:

1. Drain a queue with poll(). Repeatedly polling returns elements in priority order, but empties the queue.
2. Sort a copy. Copy the elements into a list and sort that list with the desired ordering, preserving the original queue.

A PriorityQueue does not provide a sorted view of all its elements. Printing the queue directly is not a reliable way to display sorted output.

Draining n elements requires \(O(n \log n)\) time because each poll is \(O(\log n)\). A benefit of the heap approach is that a program can stop after retrieving only the first few elements when it needs only the highest-priority items.

9. Natural Ordering and Comparable

The no-argument constructor uses natural ordering. The elements must be mutually comparable when they are placed in the queue.

Common Java types such as Integer, Double, and String implement Comparable. With integers, natural order is ascending numeric order. With strings, it is lexicographic order based on their compareTo() behavior.

For a custom class, natural ordering can be provided by implementing Comparable<T>. Its compareTo() method should define a consistent ordering for instances of that type.

If the element type does not provide a suitable natural ordering, or the application needs a different priority rule, supply a Comparator when constructing the queue instead.

A comparison should be consistent and should not depend on mutable state that changes unpredictably while elements remain in the queue. Changing a field used by the ordering after insertion can leave the heap's arrangement inconsistent with the new values. If priority changes, remove and reinsert the item or rebuild the queue using the updated priorities.

10. Using Comparator to Create a Max-Heap

By default, the smallest element is at the head. To make the largest element come out first, use a reverse-order comparator:

Output:

40
20
10

The comparator reverses the natural order. From the queue's perspective, the largest numeric value ranks first.

A comparator can also rank custom objects. For example, a task queue might rank jobs by urgency, a product queue by sales count, or an event queue by scheduled time. The comparator defines what “first” means.

Comparator ties

If two elements compare as equal, their relative order is not guaranteed unless the comparator explicitly breaks ties. A PriorityQueue can still hold multiple elements that compare as equal; unlike a TreeSet, it does not use comparator equality to enforce uniqueness.

If a deterministic tie order is required, add a secondary comparison criterion, such as a sequence number or timestamp. This is especially useful when tasks with the same priority should be processed in arrival order.

11. Constructors and Initial Capacity

PriorityQueue offers several constructors for common use cases.

The default initial capacity is 11. The internal array grows automatically when needed, so the initial capacity is a sizing hint rather than a maximum queue size.

If the approximate number of elements is known, choosing an appropriate initial capacity can reduce resizing during loading. It does not change the ordering rule or the fundamental complexity of heap operations.

Creating a queue from a known collection can use a heap-building process that takes \(O(n)\) time, rather than inserting every element individually, which can take \(O(n \log n)\) time in total.

12. Null Values and Empty Queues

A PriorityQueue does not permit null elements. Inserting null throws NullPointerException.

The queue must compare elements to preserve its heap invariant, and null does not have a natural ordering relative to ordinary non-null values. Rejecting null also allows peek() and poll() to use null to mean that the queue has no head.

This distinction is important:

• poll() returning null means the queue was empty.
• peek() returning null means there was no head to inspect.
• Inserting null is invalid and causes an exception.

When the program needs a marker for “no task,” keep that marker outside the queue or use an explicit wrapper/state field instead of inserting null.

13. Empty Queue: poll/peek Versus remove/element

Queue methods come in two behavioral families:

For most processing loops, poll() is convenient because the loop can stop when it returns null:

Integer value;
while ((value = priorities.poll()) != null) {
    // Process value
}

Use remove() or element() when an empty queue indicates a condition that should be surfaced as an exception. Choose based on the application's expected control flow rather than treating one family as universally better.

14. Time Complexity and Performance

The heap structure makes the core operations efficient, but not every operation has the same cost.

A priority queue is a strong choice when the program repeatedly needs the current minimum or maximum. It is less suitable when arbitrary membership tests or arbitrary removals dominate the workload.

If the program only needs to sort all elements once, sorting a list may be simpler. If it needs unique sorted values and navigation/range operations, TreeSet may be more appropriate. If it needs FIFO processing, use a conventional queue such as ArrayDeque.

15. Top-K Problems: Keeping the Best K Elements

A particularly useful application is finding the k largest values in a large stream without sorting the entire input.

Use a min-heap whose size is limited to k:

1. Insert each incoming value.
2. If the heap grows beyond k, remove its smallest element.
3. After processing all values, the heap contains the k largest values seen so far.

The head is the smallest value among the current top k. It acts as a cutoff: any value below that threshold cannot belong in the retained top k while the current values remain larger.

For n input values and a heap of size k, this approach takes approximately \(O(n \log k)\) time and \(O(k)\) additional space. It is often more efficient than sorting all n values when k is much smaller than n.

When the final heap is drained, values come out from smallest to largest among the retained top k. If the application requires descending output, reverse the resulting list or use an appropriate output ordering.

16. Scheduling and Event Processing

Priority queues are useful whenever the next item should be chosen by a ranking rule.

Task scheduling

A system may rank urgent tasks ahead of routine tasks. Each task can store a priority, and a comparator can order tasks by that priority. The queue then exposes the most urgent task at its head.

Event simulation

An event-driven system often needs to process the event with the earliest scheduled time. A priority queue ordered by event time lets the system retrieve the next event efficiently. As events are added, the heap maintains the earliest event at the head.

Graph algorithms

Dijkstra's shortest-path algorithm repeatedly selects the unvisited vertex with the smallest known tentative distance. A min-priority queue helps retrieve that candidate efficiently. Practical implementations must also account for updated distances—for example, by inserting a new candidate and ignoring stale entries when removed, or by using a data structure with an appropriate decrease-key operation.

These examples share the same principle: the queue is valuable because it can repeatedly return the best-ranked current candidate without sorting the entire collection after every change.

17. Common Mistakes to Avoid

Assuming the queue is FIFO

Insertion order does not determine removal order. The configured comparator determines which element comes first.

Assuming iteration is sorted

The heap array only satisfies the heap property. Use repeated poll() calls or sort a copy when sorted output is required.

Expecting contains() to be constant time

The heap is optimized for access to the head, not arbitrary lookup. contains() is \(O(n)\).

Inserting null

PriorityQueue rejects null. Use a non-null task object or manage “no value” separately.

Changing an item's priority while it is stored

If a comparator depends on a field that changes after insertion, the heap may no longer reflect the correct priority. Remove and reinsert the item or rebuild the queue after changing its priority.

Expecting stable order for equal priorities

Elements that compare equally do not necessarily come out in arrival order. Add a secondary comparison key if stable tie-breaking is a requirement.

Using a max-heap when the algorithm needs a min-heap

The default is a min-heap. Check the comparator carefully, particularly in top-K algorithms and scheduling logic.

18. Choosing the Right Collection

Choose a collection according to the operation the application performs most often. A priority queue is not a replacement for every queue or sorted collection; it is specialized for repeatedly selecting the current element with the best priority.

19. Best Practices

• Program to the Queue or PriorityQueue interface where practical instead of tying all logic to unrelated implementation details.
• Use offer(), poll(), and peek() when non-throwing queue behavior fits the application.
• Provide a clear comparator for custom objects and document what “higher priority” means.
• Add a secondary comparator key when equal-priority tasks need deterministic ordering.
• Avoid changing fields used by the comparator while an element remains in the queue.
• Do not depend on the iterator or toString() output being sorted.
• Use a min-heap of size k for top-K largest-value problems when that is more efficient than sorting all input.
• Consider initial capacity when the expected size is known and resizing overhead matters.
• Choose another collection if arbitrary lookups, frequent arbitrary removals, FIFO ordering, or a fully sorted view are the dominant requirements.

20. Quick Revision

• PriorityQueue implements Queue, but it does not guarantee FIFO removal order.
• The default queue is a min-heap, so the smallest element is at the head.
• The internal binary heap is represented using an array.
• offer() and poll() take \(O(\log n)\) time; peek() takes \(O(1)\).
• contains() and remove(Object) take \(O(n)\).
• Iteration does not guarantee sorted order.
• Comparator.reverseOrder() can create a max-heap for naturally ordered values.
• Duplicate elements are allowed, but null elements are not.
• A queue built from a collection can be heapified in \(O(n)\) time.
• Top-K selection, scheduling, event ordering, and graph algorithms are common use cases.

21. Conclusion

Java's PriorityQueue is designed for situations where the next element must be selected by priority rather than insertion order. Its binary min-heap keeps the smallest element at the head by default, allowing efficient insertion, head inspection, and head removal.

The most important concepts are the heap invariant, the distinction between heap order and fully sorted order, the role of Comparator, and the different performance costs of head operations versus arbitrary searches. Understanding these details makes it easier to choose PriorityQueue appropriately and avoid common errors in scheduling, top-K selection, and other algorithms.

For ExamAdda learners, the central rule is simple: use PriorityQueue when you repeatedly need the currently highest-ranked element. Use a FIFO queue when arrival order matters, and use a sorted collection or sorted list when you need all elements displayed in order.