Time Complexity of PriorityQueue Operations
You'll learn why some PriorityQueue operations are instant while others require logarithmic time.
Understanding the Cost of Each Operation
Not all PriorityQueue operations take the same amount of time. Because a PriorityQueue is backed by a binary heap data structure, the time complexity varies depending on whether the heap needs rebalancing.
offer() and poll(): O(log n)
Both offer() and poll() have a time complexity of O(log n), where n is the number of elements in the queue. Why? Because these operations modify the heap structure:
- offer() adds an element at the end of the heap, then "bubbles up" by repeatedly comparing with parent nodes and swapping if necessary. In the worst case, this travels from the bottom to the top of the tree.
- poll() removes the root (the highest-priority element), replaces it with the last element, then "bubbles down" by comparing with child nodes and swapping to restore heap order.
Since a binary heap has a height of log₂(n), these rebalancing operations take at most log n steps.
peek(): O(1)
The peek() operation is O(1) — constant time. It simply returns the element at the root of the heap without any modifications. No rebalancing is needed, so it's just a direct array access.
Think of it like this: Imagine a tournament bracket where the champion is always at the top. Looking at who the champion is (peek) takes one glance. But adding a new competitor (offer) or removing the champion and finding the next winner (poll) requires reorganizing matches up or down the bracket.
Why This Matters
Understanding these complexities helps you choose the right data structure. If you need frequent access to the minimum/maximum element without removal, PriorityQueue is excellent. If you need O(1) insertions and removals, consider a LinkedList instead.
Key Takeaway: In PriorityQueue, offer() and poll() are O(log n) due to heap rebalancing, while peek() is O(1) since it only reads the root without modifications.