ReviseAlgo Logo

Collections Framework

PriorityQueue

Analyze PriorityQueue structures, binary heap array representations, and priority ordering.

Interview: Focuses on binary heap properties, O(log N) insert/delete, O(1) peek, and Comparable/Comparator usage.

Last Updated: June 13, 2026 • 10 min read

A PriorityQueue is an unbounded queue backed by a balanced binary heap. Elements are processed according to their priority, which is determined by their natural ordering or a custom Comparator.

Min-Heap Array

Stored as a balanced binary tree packed into a single array, keeping the lowest element at the root node (index 0).

Heapify Cost

Adding (offer) or removing (poll) elements requires rebuilding the heap, taking O(log N) time.

Constant Peek

Retrieving the head element (peek()) takes constant O(1) time because the minimum element is always at index 0.

Heap Array Representation and Unsorted Iteration

PriorityQueue uses a min-heap structure, which affects how it is traversed:

  • Binary Heap Array: Elements are arranged such that for index i, children are located at 2i + 1 and 2i + 2.
  • Unsorted Iterator: Iterating over a PriorityQueue directly (e.g. using an iterator or for-each loop) does not guarantee sorted order. It simply traverses the backing array. To retrieve elements in sorted order, you must call poll() in a loop.

Common Pitfalls

  • Iterating to print sorting: Printing a PriorityQueue using an enhanced for-loop and expecting sorted order. It will output the array layout instead.
  • Inserting non-comparables: Adding custom classes that do not implement Comparable, which throws a ClassCastException at runtime.

Best Practices

  • Use poll() for sorted processing: Always use poll() in a loop to process elements in priority order.
  • Null Rejection: Do not insert nulls into a PriorityQueue, as they prevent priority comparisons.

Interview-Relevant Information

Q1: What is the underlying data structure of PriorityQueue?
Answer: A balanced binary heap represented as a native array. The root element (minimum element for min-heap) is stored at index 0.

Q2: Why does iterating over PriorityQueue print elements in unsorted order?
Answer: The PriorityQueue iterator traverses the underlying array directly, which is organized as a binary heap, not a sorted list. To process elements in priority order, they must be removed using poll().

Quick Checklist

Can you state the underlying structure of PriorityQueue, list complexities of poll vs peek, and explain why iteration does not match priority order? If yes, you understand PriorityQueue.

Use Cases

Implementing Huffman encoding systems for text compression.

Building task schedulers where tasks are processed based on numerical priorities.

Common Mistakes

Expecting for-each loops to traverse PriorityQueues in sorted order.

Attempting to insert null values into PriorityQueue.