Unravel โบ Java concepts โบ Collections and streams
PriorityQueue and heaps
A PriorityQueue always hands out the smallest element first (or the largest with a reversed comparator), whatever order you added them in.
Learn these first
At a glance
A hospital waiting room: patients are not served by arrival time but by urgency, and the most urgent one is always next.
- 1offer(x) inserts in O(log n); poll() removes and returns the smallest in O(log n); peek() reads it in O(1)
- 2Order comes from Comparable or a comparator: new PriorityQueue<>((a, b) -> b - a) or Comparator.reverseOrder() makes it a max-heap
- 3Typical uses: "top K" problems (keep a heap of size K), scheduling by deadline, merging sorted lists, Dijkstra's shortest path, running median with two heaps
- Iterating a PriorityQueue or printing it does not show sorted order: only the head is guaranteed to be the smallest
- remove(Object) and contains are O(n)
- A binary heap stored in an Object[]: the children of index i are 2i+1 and 2i+2
import java.util.*;public class TopK { static List<Integer> largest(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); for (int n : nums) { heap.offer(n); if (heap.size() > k) heap.poll(); } List<Integer> out = new ArrayList<>(heap); out.sort(Comparator.reverseOrder()); return out; }}- line 4 uses PriorityQueue, the core of PriorityQueue and heaps
Read the full explanation (about 1 min)
A PriorityQueue always hands out the smallest element first (or the largest with a reversed comparator), whatever order you added them in. It is Java's ready-made heap.
A mental model
A hospital waiting room: patients are not served by arrival time but by urgency, and the most urgent one is always next.
How it works
offer(x) inserts in O(log n); poll() removes and returns the smallest in O(log n); peek() reads it in O(1).
Order comes from Comparable or a comparator: new PriorityQueue<>((a, b) -> b - a) or Comparator.reverseOrder() makes it a max-heap.
Typical uses: "top K" problems (keep a heap of size K), scheduling by deadline, merging sorted lists, Dijkstra's shortest path, running median with two heaps.
Going deeper
Iterating a PriorityQueue or printing it does not show sorted order: only the head is guaranteed to be the smallest. Poll in a loop to get sorted output.
remove(Object) and contains are O(n). If priorities change after insertion, the heap is not re-ordered: remove and re-add the element.
It is not thread safe and not stable: equal priorities come out in arbitrary order. Add a sequence number to the comparator when you need first-come-first-served among equals.
Under the hood
A binary heap stored in an Object[]: the children of index i are 2i+1 and 2i+2. Insert places the element at the end and sifts it up; poll moves the last element to the root and sifts it down.
Common mistakes
- Expecting the iterator to be sorted.
- Changing an element's priority in place.
- Using subtraction in the comparator and overflowing.
How Unravel recognises it
When you paste code, Unravel looks for these signs of priorityqueue and heaps. Spotting them yourself is a good habit when you read unfamiliar code:
- Types:
PriorityQueuePriorityBlockingQueue - Created with new:
PriorityQueue
Part of a learning path
- Collections in depth ยท previous: Queue, Deque and Stack ยท next: Iterator and Iterable
Related concepts
Frequently asked questions
What is PriorityQueue and heaps?
A PriorityQueue always hands out the smallest element first (or the largest with a reversed comparator), whatever order you added them in. It is Java's ready-made heap.
What are the most common mistakes with PriorityQueue and heaps?
Expecting the iterator to be sorted. Changing an element's priority in place. Using subtraction in the comparator and overflowing.
How can I see PriorityQueue and heaps in real code?
Paste your own Java into Unravel and it will point out where priorityqueue and heaps appears, explain how it works at the detail level you choose, and draw the flow of the code around it.