PriorityQueue — heaps in disguise
Binary heaps, O(log n) insert and extract-min, and the canonical k-largest pattern.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
The heap property
A binary heap is a complete binary tree where every parent is smaller than its children (min-heap) or larger (max-heap). Java stores it as a plain array — parent at index i, children at 2i+1 and 2i+2 — which is compact and cache-friendly. The root is always the smallest (or largest) element.
Operations
offer(v) inserts at the end and bubbles up until the heap property holds — O(log n). poll() removes the root, moves the last element to the top, and sinks it down — also O(log n). peek() is O(1). Iteration order is *not* sorted; if you want elements in order, call poll repeatedly.
K-largest in O(n log k)
Keep a min-heap of size k. For each incoming element, offer it. If the heap exceeds size k, poll the smallest. When you're done, the heap contains the k largest values, and you used O(k) memory — much better than sorting the whole input to grab the top k.
Custom ordering with Comparator
Default is min-heap by natural order. For a max-heap of integers, pass Comparator.reverseOrder(). For custom types, pass any Comparator — Comparator.comparingInt(Task::priority) is idiomatic.
Runs on a sandboxed JVM via the public Piston API. Edit the code and hit Run.
Dijkstra and A*
Nearly every shortest-path algorithm uses a priority queue. Dijkstra offers each vertex with its tentative distance and polls the closest unvisited vertex next. A* does the same, weighted by a heuristic. If your queue keys change frequently, plain PriorityQueue doesn't support decrease-key — the workaround is to re-offer with the new priority and ignore stale entries when polled.
What it isn't
A PriorityQueue is not a FIFO queue — elements come out in priority order, not arrival order. It's not thread-safe either; use PriorityBlockingQueue for concurrent use.
Related lessons & next topics
Keep going — these pair well with PriorityQueue.
- § 6.01 · Data Structures in JavaArrays and ArrayList — the workhorses
Fixed-size arrays vs dynamic ArrayList. Memory layout, amortized O(1) append, and when each one shines.
Beginner · 22 min - § 6.02 · Data Structures in JavaLinkedList and the Deque interface
Doubly-linked nodes, O(1) insert at either end, and why LinkedList is almost never the right choice.
Beginner · 20 min - § 6.03 · Data Structures in JavaStacks, queues, and ArrayDeque
LIFO, FIFO, and why java.util.Stack is a historical mistake you should avoid.
Intermediate · 24 min - § 6.04 · Data Structures in JavaHashMap, equals, and hashCode
How hashing works, why you must override equals and hashCode together, and the load factor that keeps lookups O(1).
Intermediate · 28 min