DSA in Java: Heaps & Priority Queues (Beginner Guide)

Sometimes you don't need all your data sorted — you just need quick access to the smallest or largest item, over and over. That's exactly what a heap (and its friendly Java wrapper, the PriorityQueue) is built for. Heaps power scheduling, "top K" problems, and famous algorithms like Dijkstra's shortest path. Let's make them approachable.

The problem heaps solve

Suppose you're running a hospital ER: patients should be seen by severity, not arrival order. Or you want the 3 highest scores from a live stream of millions. Re-sorting the whole collection every time something changes would be wasteful. A heap keeps the "most important" item ready at the top at all times, with efficient inserts and removals.

What is a heap?

A heap is a special binary tree that follows one simple rule (we'll use a min-heap, which keeps the smallest on top):

Note this is a weaker rule than a BST — a heap isn't fully sorted, it just guarantees the min (or max) is on top. That weaker promise is what makes it so fast to maintain.

See how each parent is smaller than its children (2 < 5, 8; 5 < 9, 7), but the tree isn't fully sorted? That's a heap. (Fun fact: heaps are usually stored compactly in a plain array, no node objects needed — but you rarely need to worry about that detail.)

The operations (and their speed)

Getting the most important item is instant; adding and removing are fast O(log n). That's the sweet spot heaps occupy.

Java's PriorityQueue: the heap you'll actually use

You almost never build a heap by hand — Java's PriorityQueue is a ready-made min-heap:

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);

minHeap.peek();   // 2 — smallest, without removing (O(1))
minHeap.poll();   // 2 — remove & return smallest (O(log n))
minHeap.poll();   // 5 — next smallest

Want a max-heap (largest on top) instead? Just hand it a reversed comparator:

PriorityQueue<Integer> maxHeap =
    new PriorityQueue<>(Collections.reverseOrder());
// now poll() returns the LARGEST each time

The classic use: "Top K" problems

A hugely common interview task: "find the K largest (or smallest) elements." The elegant trick uses a heap of size K, so you never sort the whole input — giving O(n log k), much better than sorting everything:

// Find the K largest numbers using a MIN-heap of size k
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int num : nums) {
    heap.offer(num);
    if (heap.size() > k) {
        heap.poll();   // drop the smallest → keep only the k largest
    }
}
// heap now holds the k largest elements

The idea: keep only k items; whenever the heap grows past k, throw away its smallest. What survives are the k biggest. Clever, and a genuine interview favourite.

Heaps intimidated me at first because the internal "bubble up / bubble down" mechanics sounded complex. Then I realised: for interviews and real work, I almost never implement those mechanics — I just use PriorityQueue and remember two things: (1) peek gives me the min/max instantly, and (2) reversing the comparator flips min-heap to max-heap. That's 90% of what you need. When a problem says "smallest so far," "largest so far," "top K," or "by priority," reach for a PriorityQueue and you're most of the way there.

Key takeaways

• A heap keeps the min (or max) always at the top; peek is O(1), insert/remove are O(log n).
• It's a weaker promise than a full sort — only the top is guaranteed — which is what makes it fast.
• Use Java's PriorityQueue (a min-heap); pass Collections.reverseOrder() for a max-heap.
• Heaps shine on "Top K" problems and priority scheduling (schedulers, Dijkstra, merging streams).

← Previous: DSA Lesson 10 — Trees & BSTs
Next: DSA Lesson 12 — Graphs (BFS & DFS) →
↑ Back to the DSA roadmap