What are the time complexities of PriorityQueue's offer, poll, peek, and contains/remove(Object) operations, and why?
answer
- Heap height = log n drives the log-n ops
- peek O(1): head at index 0
- offer sift-up, poll sift-down -> O(log n)
- contains/remove(Object) O(n): linear scan
- Build-from-collection is O(n) heapify; no decrease-key
basics
~20 soffer and poll are O(log n) because they bubble an element up or down the heap. peek is O(1) - the head is at index 0. contains(o) and remove(o) are O(n) because they have to scan the array linearly.
solid answer
~50 sPriorityQueue is a binary heap on an array, so costs follow heap mechanics. peek() is O(1): the head is always at index 0. offer(e) is O(log n): it appends at the end then sift-ups, swapping with its parent until the heap property holds - at most tree-height swaps. poll() is O(log n): it removes the root, moves the last element to the top, then sift-downs. The general remove(Object o) and contains(o) are O(n) because there's no index by value - they linearly search the array, and remove then re-heapifies. size/isEmpty are O(1). Building a heap from a collection (the constructor that takes a Collection) is O(n) via bottom-up heapify, cheaper than n separate O(log n) inserts. There is no efficient decrease-key, which is why textbook Dijkstra in Java is usually done by inserting duplicates and skipping stale entries rather than updating priorities in place.
go deeper
Knows peek is fast and poll/offer are logarithmic, even if not the exact reasons.
States O(1)/O(log n)/O(n) for the main ops and connects O(log n) to heap height.
Explains sift-up/sift-down, the O(n) linear scan for contains/remove(Object), and O(n) bulk heapify with reasoning.
Discusses the decrease-key gap, lazy-deletion Dijkstra pattern, amortized resize cost, and when an indexed/Fibonacci heap or TreeSet is a better structure.
## Setup: it's a heap on an array Every cost below comes from one fact: `PriorityQueue` stores a **binary heap** in an array. A binary heap is a *complete* binary tree (filled left-to-right, every level full except possibly the last), which means its **height is ⌊log₂ n⌋** for n elements. Operations that walk from a node to the root or to a leaf therefore do at most ~log n steps. "O(log n)" means the work grows with the logarithm of size - doubling the elements adds only one extra level of work. ## peek() - O(1) The head (the minimum, or your Comparator's first element) is *always* stored at array index 0. Returning it is a single array read - constant time, independent of size. ## offer(e) / add(e) - O(log n) 1. The element is placed at the **end** of the array (the next free leaf slot). 2. It then **sift-ups** (a.k.a. bubble-up / percolate-up): compare it with its parent at `(i-1)/2`; if it's smaller (higher priority), swap; repeat until it's >= its parent or reaches the root. The number of swaps is bounded by the tree height, so O(log n). (Amortized, occasional array resizing adds an O(n) copy now and then, but amortized it stays O(log n).) ## poll() / remove() - O(log n) 1. Save the root (index 0) - that's the return value. 2. Move the **last** array element into index 0. 3. **Sift-down** (bubble-down): compare it with its smaller child; if it's larger, swap with that child; repeat until both children are >= it or it becomes a leaf. Again bounded by height: O(log n). ## contains(Object) and remove(Object) - O(n) A heap is indexed by *position*, not by *value*. There is no hash or sorted lookup, so to find an arbitrary element you must **linearly scan** the array: O(n). `remove(Object o)` then removes that slot and re-heapifies the disturbed subtree (O(log n)), but the dominant cost is the O(n) search. `contains` is likewise O(n). ## Bulk construction - O(n), not O(n log n) The constructor `new PriorityQueue<>(someCollection)` doesn't insert one-by-one. It copies the elements then runs **bottom-up heapify** (sift-down from the last internal node up to the root). A tight analysis shows this is **O(n)** total - cheaper than n separate O(log n) `offer` calls (which would be O(n log n)). ## size() / isEmpty() - O(1) The queue tracks its element count in a field. ## The missing operation: decrease-key Classic graph algorithms (Dijkstra, Prim) want to **lower the priority of an element already in the queue** in O(log n). `PriorityQueue` offers no such operation - you'd have to `remove(o)` (O(n)) then re-`offer`. The idiomatic Java workaround is the **lazy/stale-entry** technique: just `offer` a new entry with the better priority and, when you `poll` an element whose recorded distance is worse than the best you've already finalized, skip it. This keeps each op O(log n) at the cost of extra entries. ## Summary table | Operation | Cost | Why | |---|---|---| | peek | O(1) | head at index 0 | | offer/add | O(log n) | sift-up by height | | poll/remove() | O(log n) | sift-down by height | | contains / remove(Object) | O(n) | linear scan | | construct from Collection | O(n) | bottom-up heapify | | size/isEmpty | O(1) | counter field |
- Why does building a heap from n elements cost O(n) rather than O(n log n)?Bottom-up heapify sift-downs nodes, but most nodes are near the bottom with tiny subtrees; the summed work over all levels converges to O(n), not O(n log n).
- How do you implement Dijkstra in Java without a decrease-key operation?Insert a fresh (node, newDistance) entry whenever you relax an edge; when you poll an entry whose distance is worse than the node's finalized distance, discard it as stale. Each op stays O(log n).
saying these in an interview costs you the question
- Claiming poll is O(1) (only peek is)
- Saying contains/remove(Object) is O(log n) - it's O(n)
- Believing building a heap from a list is O(n log n) (it's O(n))
- Assuming PriorityQueue supports an efficient decrease-key