PriorityQueue internal implementation.

Hook: Interviewers love this question because PriorityQueue looks like a simple queue, but the hidden heap rules explain almost every behavior and gotcha.

Question: PriorityQueue internal implementation.

Answer: In Java, PriorityQueue is backed by a binary heap, which is a complete tree stored inside an array. By default it is a min-heap, so the smallest element is always at the head, but the rest of the elements are only partially ordered. That is why peek() is fast, while offer() and poll() do a little reordering work.

Interview-Ready Answer: I’d say: Java’s PriorityQueue is implemented as a binary heap stored in an array. The head is the smallest element by natural order or by the provided Comparator, so peek() is O(1) and offer()/poll() are O(log n). The important gotcha is that iteration is not sorted, nulls are forbidden, and the queue is not thread-safe.

What it is

A PriorityQueue is a queue where the next element removed is the one with the highest priority according to an order rule. In Java, that rule comes from natural ordering (Comparable) or a supplied Comparator, which is a small object that defines how two values should be ranked. Internally, Java does not keep the whole structure sorted; it only guarantees that the head is the best element.

How it works under the hood

1. The data is stored in a zero-based array. A binary heap is a complete binary tree, meaning every level is full except possibly the last, and the last level is filled from left to right.
2. For an element at index i, the parent is at (i - 1) / 2, the left child at 2i + 1, and the right child at 2i + 2. This index math is why arrays are such a good fit.
3. On offer(), the new element is appended at the end of the array. Then Java performs sift up (also called bubble up): it compares the element with its parent and swaps upward until the heap rule is restored.
4. On peek(), Java simply reads index 0. The root of the heap is always the minimum element in a min-heap, so this is constant time.
5. On poll(), Java removes the root, moves the last array element into index 0, shrinks the size, and then performs sift down: it compares the new root with its children and swaps with the smaller child until the heap rule is restored.
6. If you build the queue from another collection, Java can heapify it bottom-up. Heapify means restoring the heap property for all nodes starting from the last parent toward the root, and it runs in O(n), which is faster than inserting one item at a time.
7. The backing array grows automatically. The default initial capacity is 11, and the array expands as needed; the important idea is that inserts stay amortized efficient, where amortized means the average cost over many operations, even if one resize is expensive.

Why use it

Use a PriorityQueue when you repeatedly need the next smallest or largest item: task scheduling, Dijkstra’s algorithm, event simulation, rate limiting, or top-K problems. Use it when you care about the head, not about scanning everything in order.

Performance and edge cases

• peek(): O(1)
• offer() and poll(): O(log n), because the element may travel up or down the heap height
• contains() and remove(Object): O(n), because the queue must linearly search for the matching element
• Nulls are forbidden; offer(null) throws NullPointerException
• Iteration order is not priority order; the iterator walks the internal array, not a sorted view
• It is not thread-safe; for concurrent producer/consumer use cases, consider PriorityBlockingQueue

Memory hook for the mechanism: the parent only needs to outrank its children; siblings do not need to be ordered. That one rule is the whole heap.

Real-World Story: In a checkout service, the team used a PriorityQueue to schedule payment retries, fraud checks, and inventory refresh jobs. A bug appeared when engineers iterated the queue with a for-each loop, assuming that iteration would return jobs in priority order. It does not, so urgent payment retries were processed behind low-priority work; users saw checkout timeouts, logs showed jobs handled in a seemingly random order, and retry traffic spiked because the queue was being drained incorrectly.

Follow-up & Tricky Questions:

• How does Java keep the heap property? It uses sift up after insertion and sift down after removal. Those swaps only travel along the height of the tree, which is why the main operations are O(log n).
• What is the complexity of building a PriorityQueue from a collection? Java can heapify bottom-up in O(n). That is better than inserting each element one by one, which would cost O(n log n).
• How do you make it behave like a max-heap? Supply a reverse comparator, for example Comparator.reverseOrder() for naturally ordered types. Then the largest element becomes the head.
• Why is iteration not sorted? Because the iterator walks the internal array layout, not a fully sorted structure. If you need sorted output, keep polling a copy of the queue.
• When should you use PriorityBlockingQueue instead? Use it when multiple threads add and remove elements concurrently. PriorityQueue itself is not thread-safe, so external locking or a concurrent alternative is needed.
• Does peek() throw when empty? No, it returns null; element() throws NoSuchElementException. That difference is a classic interview trap.
• Can PriorityQueue store null? No, it rejects null elements immediately with NullPointerException. The queue uses null internally to represent an empty slot, so null data would break the structure.
• Does contains() use the heap order? No, it scans linearly. The heap only gives fast access to the head, not fast lookup by value.

Common Mistakes:

• Mistake: Saying the queue is fully sorted. Correction: Only the head is guaranteed to be the smallest or largest element; the rest are only heap-ordered.
• Mistake: Using a for-each loop to process tasks by priority. Correction: Iterate only if order does not matter; otherwise repeatedly poll() a copy.
• Mistake: Claiming all operations are O(1). Correction: peek() is O(1), but offer() and poll() are O(log n).
• Mistake: Forgetting about nulls and thread safety. Correction: PriorityQueue rejects nulls and needs external synchronization in concurrent code.

Memory Hook: Think of a family tree where every parent only has to outrank its children; siblings can be messy. That is a heap.

Cheat Sheet:

• Backed by an array-based binary heap.
• Default is a min-heap; comparator can change the order.
• peek() is O(1); offer() and poll() are O(log n).
• Heapify from a collection is O(n).
• Iteration is not sorted.
• Nulls are not allowed; not thread-safe.

Practice Tasks:

• Write a max-heap PriorityQueue for integers using Comparator.reverseOrder().
• Copy a queue, poll all elements, and print them in priority order.
• Measure the difference between inserting 100000 items one by one versus building from a collection.