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.