What Is a Heap?

The most urgent thing first

In a hospital emergency room, patients aren't seen in arrival order – the most urgent is seen first. We need a structure that can quickly add an item and quickly remove the smallest (most urgent). That's a priority queue, and the usual way to build one is a heap.

The heap rule

A min-heap is a binary tree where every parent is smaller than (or equal to) its children. So the smallest item is always at the root. It is not fully sorted – only “parent ≤ children” matters.

A heap is filled level by level, left to right, so it fits neatly in an array with no gaps. For the item at index i:

• its children are at 2*i + 1 and 2*i + 2,
• its parent is at (i - 1) / 2.

Think of it like this: A company where every manager is senior to their team. You don't know how two people in different teams compare – but the CEO at the top is the most senior of all.

Build a tiny min-heap

Add: put the item at the end, then swap it up while it's smaller than its parent. Remove: take the root, move the last item to the root, then swap it down with its smaller child while it's bigger. Each path is only as long as the tree's height: O(log n).

import java.util.ArrayList;

class MinHeap {
    private ArrayList<Integer> a = new ArrayList<Integer>();

    private void swap(int i, int j) {
        int t = a.get(i); a.set(i, a.get(j)); a.set(j, t);
    }

    void add(int x) {
        a.add(x);
        int i = a.size() - 1;
        while (i > 0 && a.get(i) < a.get((i - 1) / 2)) {      // smaller than parent: swim up
            swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    int removeMin() {
        int min = a.get(0);
        int last = a.remove(a.size() - 1);
        if (!a.isEmpty()) {
            a.set(0, last);
            int i = 0;
            while (true) {                                     // sink down
                int l = 2 * i + 1, r = 2 * i + 2, small = i;
                if (l < a.size() && a.get(l) < a.get(small)) small = l;
                if (r < a.size() && a.get(r) < a.get(small)) small = r;
                if (small == i) break;
                swap(i, small);
                i = small;
            }
        }
        return min;
    }

    boolean isEmpty() { return a.isEmpty(); }
    public String toString() { return a.toString(); }
}

public class Main {
    public static void main(String[] args) {
        MinHeap heap = new MinHeap();
        int[] values = {40, 10, 30, 5, 20};
        for (int v : values) {
            heap.add(v);
            System.out.println("add " + v + " -> array " + heap);
        }
        StringBuilder out = new StringBuilder();
        while (!heap.isEmpty()) out.append(heap.removeMin()).append(' ');
        System.out.println("removed in order: " + out.toString().trim());
    }
}

Output

add 40 -> array [40]
add 10 -> array [10, 40]
add 30 -> array [10, 40, 30]
add 5 -> array [5, 10, 30, 40]
add 20 -> array [5, 10, 30, 40, 20]
removed in order: 5 10 20 30 40

Look at the arrays: they're not sorted, but index 0 is always the smallest – and removing items one by one gives them back in sorted order (that's heap sort, O(n log n)).