Heaps & Priority Queues

Introduction

In a standard Queue, elements are processed First In, First Out (FIFO). But the real world rarely works purely on arrival time.

Imagine an A&E (Emergency Room) waiting area:

1. A patient arrives with a sprained ankle.
2. A second patient arrives with a paper cut.
3. A third patient arrives with a heart attack.

Even though the heart attack patient arrived last, they must be treated first because they have the highest priority. A data structure that enforces this rule is called a Priority Queue.

Under the hood, Priority Queues are almost always powered by a magical tree structure called a Heap.

What is a Heap?

A Heap is a Binary Tree with two very strict rules:

1. Shape Property: It must be a Complete Binary Tree. Every level of the tree is fully filled, except possibly the last level, which is filled from left to right with no gaps.
2. Order Property:
   • In a Max-Heap, the parent is always $\ge$ its children. The largest element is at the root.
   • In a Min-Heap, the parent is always $\le$ its children. The smallest element is at the root.

The Max-Heap Visualised

Notice that unlike a Binary Search Tree, there is no rule about the left child being smaller than the right child. 80 is smaller than 90, but 50 is larger than 20. The only rule is parent layer > child layer.

The Array Secret

Here is the most brilliant part about a Heap: because it is a Complete Binary Tree with no gaps, we do not need Node objects or pointers. We can squish the entire tree perfectly into a flat Array!

If the Parent is at index i:

• Left Child is at index 2i + 1
• Right Child is at index 2i + 2
• Parent of any child is at (i - 1) / 2

Tree:       [100]
           /     \
         [80]    [90]
         /  \    /  \
       [50][70][20][40]

Array: [100, 80, 90, 50, 70, 20, 40]
Index:   0   1   2   3   4   5   6

Check the maths: the left child of 80 (index 1) is at $2(1) + 1 = 3$. Value at index 3 is 50. It works perfectly!

Core Operations (Max-Heap)

1. Peek (Get Max) — $O(1)$

Because the maximum value is always at the root, and the root is always at array[0], we can get the highest priority element instantly.

2. Insert (Push) — $O(\log n)$

1. Add the new element to the very end of the array (bottom-left of the tree).
2. “Bubble Up”: If the new element is larger than its parent, swap them.
3. Keep swapping upwards until the heap property is restored.

Let’s insert 95:

• Add 95 at the end (index 7, left child of 50).
• 95 > 50? Yes, swap.
• 95 > 80? Yes, swap.
• 95 > 100? No, stop. 95 is in its correct place. (Takes at most $\log n$ swaps, since the tree height is $\log n$).

3. Extract Max (Pop) — $O(\log n)$

1. Remove the root (100).
2. Take the very last element in the array (40) and move it to the root.
3. “Bubble Down”: The new root (40) is smaller than its children (95 and 90). Swap it with its largest child (95).
4. Keep swapping downwards until it is larger than its children.

Java Implementation (Priority Queue)

You almost never have to build a heap from scratch using an array. Java provides the PriorityQueue class, which is a Min-Heap by default.

import java.util.PriorityQueue;
import java.util.Collections;

public class HeapExample {
    public static void main(String[] args) {
        // Min-Heap (Default) - smallest numbers have highest priority
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.offer(50);
        minHeap.offer(10);
        minHeap.offer(30);
        
        System.out.println("Min-Heap Peek: " + minHeap.peek()); // 10
        System.out.println("Min-Heap Poll: " + minHeap.poll()); // Removes 10
        
        
        // Max-Heap - largest numbers have highest priority
        // We pass Collections.reverseOrder() to reverse the natural ordering
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        maxHeap.offer(50);
        maxHeap.offer(10);
        maxHeap.offer(90);
        
        System.out.println("Max-Heap Peek: " + maxHeap.peek()); // 90
        System.out.println("Max-Heap Poll: " + maxHeap.poll()); // Removes 90
    }
}

When to Use / When NOT to Use

Heap Sort — The $O(n \log n)$ Bonus

Because a heap can pop the maximum element in $O(\log n)$ time, finding and removing all $n$ elements in order gives you a fully sorted array in $O(n \log n)$ time.

Better yet, because a heap stores its data entirely inside the original array (no extra memory needed), Heap Sort sorts strictly in-place with $O(1)$ extra space, unlike Merge Sort. It is slower in practice than Quick Sort, but provides a guaranteed worst-case of $O(n \log n)$.

Practice Problems

Learning to spot “Heap problems” is a superpower in interviews. Look for phrases like “Top K”, “Kth largest”, or “Merge K”.

1. Kth Largest Element in an Array – LeetCode #215 — Create a Min-Heap of size K. Offer elements, and when the heap size exceeds K, poll the minimum. The root will be your Kth largest!
2. Last Stone Weight – LeetCode #1046 — A problem literally begging to be solved with a Max-Heap.
3. Merge K Sorted Lists – LeetCode #23 — A legendary hard problem made trivial: put the heads of all K lists into a Min-Heap, pop the smallest, and push its next node back in.

What’s Next?

Trees are fantastic, but they have a limitation: a parent can point to a child, but a child can never point back up to a parent or a sibling across the tree.

If we remove this hierarchical restriction and allow any node to connect to any other node, we graduate to the ultimate data structure: Graph Representation & BFS.