Heaps & Priority Queue

A heap is a tree-shaped structure built for one job: instantly knowing the smallest (or largest) element in a collection, even as elements are added and removed. Unlike a BST, it makes no promise about ordering elements relative to each other in general — only about which single element sits on top. That narrower promise is exactly what makes heap operations fast and predictable, with none of the "it depends on insertion order" worry BSTs have.

Min-Heap vs Max-Heap

A min-heap keeps the smallest element at the root — every parent is smaller than or equal to both its children. A max-heap is the mirror image — every parent is bigger than or equal to both its children. Note this is a much weaker rule than the BST invariant: a heap says nothing about whether a node's left subtree is smaller than its right subtree, only about parent vs. child.

Array-Based Representation

Heaps are almost always implemented as a plain array, never with explicit left/right pointer objects, because a complete binary tree (every level fully filled except possibly the last, which fills left to right) has a predictable index pattern:

For example, the min-heap array [1, 3, 2, 7, 4, 5] represents this tree, where every parent is <= its children:

No pointers, no wasted memory on left/right references — just index arithmetic on a plain array.

Java's Built-In PriorityQueue

Java already ships a heap implementation, so you rarely hand-code one: java.util.PriorityQueue. By default it's a min-heap — poll() always returns the smallest element currently in the queue. Pass a custom Comparator to flip it into a max-heap.

// Default: min-heap — smallest element comes out first
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
System.out.println(minHeap.poll());  // 1 — the smallest

// Max-heap — pass Comparator.reverseOrder() to flip the ordering
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
System.out.println(maxHeap.poll());  // 5 — the largest

Time complexity: O(log n) for both offer() (insert) and poll() (extract-min/max) — each re-establishes the heap property by bubbling the changed element up or down at most the height of the tree, which is O(log n) since the tree is always complete. Space complexity: O(n) to hold n elements.

Worked Problem: Kth Largest Element

A classic heap problem: given an unsorted array, find the Kth largest element without fully sorting the array. The elegant approach uses a min-heap of size K: keep only the K largest elements seen so far, and the smallest of those K (the heap's root) is always the Kth largest overall.

public static int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();          // evict the current smallest — it can't be a top-K element
        }
    }
    return minHeap.peek();          // root of the size-k min-heap = Kth largest overall
}

Trace on nums = [3, 2, 1, 5, 6, 4], k = 2 (find the 2nd largest): offer 3 → heap {3}. offer 2 → heap {2,3}. offer 1 → heap {1,2,3}, size > 2, poll evicts 1 → heap {2,3}. offer 5 → heap {2,3,5}, size > 2, poll evicts 2 → heap {3,5}. offer 6 → heap {3,5,6}, size > 2, poll evicts 3 → heap {5,6}. offer 4 → heap {4,5,6}, size > 2, poll evicts 4 → heap {5,6}. Final peek() returns 5 — correctly the 2nd largest value in the array (largest is 6).

Time complexity: O(n log k) — n insertions, each costing O(log k) since the heap never grows past size k (this beats the O(n log n) of fully sorting when k is small). Space complexity: O(k) — the heap never holds more than k elements at once.