Implement a Maxheap MinHeap using arrays and recursion

The problem, simply

Make a box of numbers that can do three things fast:

• insert(x): put a new number in.
• peek(): tell me the biggest number without taking it out.
• extract(): take the biggest number out.

That is a max heap. A min heap is the same thing, but the smallest number sits on top. You must store it in an array and write the moves with recursion.

A story to remember it

Picture it

The pyramid is a tree, but we never build real tree nodes. We write the kids row by row into an array. Then the kid at index i has helpers at 2i + 1 and 2i + 2, and the kid above them is at (i - 1) / 2.

Examples

Way 1: the simple way

Keep the numbers in a plain list in any order.

1. insert(x): put x at the end. That is instant.
2. peek() and extract(): walk the whole list to find the biggest, then remove it.

import java.util.ArrayList;
import java.util.List;

class SlowMaxBox {
    private final List<Integer> items = new ArrayList<>();

    void insert(int x) { items.add(x); }       // instant

    int peek() {
        if (items.isEmpty()) throw new IllegalStateException("empty");
        return items.get(indexOfMax());
    }

    int extract() {
        if (items.isEmpty()) throw new IllegalStateException("empty");
        int i = indexOfMax();
        int best = items.get(i);
        items.set(i, items.get(items.size() - 1)); // fill the hole with the last one
        items.remove(items.size() - 1);
        return best;
    }

    private int indexOfMax() {                 // look at every number
        int best = 0;
        for (int i = 1; i < items.size(); i++) {
            if (items.get(i) > items.get(best)) best = i;
        }
        return best;
    }
}

How long it takes: insert is O(1), but every peek and extract walks all n numbers, O(n). Extra room: the list itself, O(n). If you take out all n numbers one by one, that is O(n^2).

Way 2: the clever way

Keep the pyramid rule: every parent beats its children. Then the winner is always at index 0, and fixing the pyramid after a change only walks one path from top to bottom, which is about log n steps.

1. insert(x): put x at the end of the array. Sift it up: if it beats its parent, swap, and call sift up again from the parent's spot.
2. extract(): save a[0]. Move the last item to index 0 and shrink the size. Sift it down: find the better of its two children; if that child beats it, swap and call sift down again from the child's spot.
3. For a min heap, flip every "beats". One small better(i, j) method does that.

import java.util.Arrays;

class Heap {
    private int[] a = new int[8];
    private int size = 0;
    private final boolean isMin;       // true: min heap, false: max heap

    Heap(boolean isMin) { this.isMin = isMin; }

    // does the item at i deserve to sit above the item at j?
    private boolean better(int i, int j) {
        return isMin ? a[i] < a[j] : a[i] > a[j];
    }

    private void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    void insert(int x) {
        if (size == a.length) a = Arrays.copyOf(a, size * 2); // grow the array
        a[size] = x;
        siftUp(size);
        size++;
    }

    private void siftUp(int i) {
        if (i == 0) return;                 // reached the top
        int parent = (i - 1) / 2;
        if (better(i, parent)) {
            swap(i, parent);
            siftUp(parent);                 // keep climbing
        }
    }

    int peek() {
        if (size == 0) throw new IllegalStateException("heap is empty");
        return a[0];
    }

    int extract() {
        int top = peek();
        a[0] = a[size - 1];                 // last item jumps to the top
        size--;
        siftDown(0);
        return top;
    }

    private void siftDown(int i) {
        int left = 2 * i + 1, right = 2 * i + 2, best = i;
        if (left < size && better(left, best)) best = left;
        if (right < size && better(right, best)) best = right;
        if (best != i) {
            swap(i, best);
            siftDown(best);                 // keep sinking
        }
    }

    int size() { return size; }
}

How long it takes: the pyramid has about log n rows, and sift up or sift down moves one row per call. So insert and extract are O(log n), and peek is O(1). Extra room: the array, O(n), plus O(log n) for the recursion calls.

Another way: build a heap from a whole array

If you already have all n numbers, inserting them one by one costs O(n log n). There is a faster trick. Pour the numbers in as they are, then fix the pyramid from the bottom up: call sift down on every node that has children, starting from the last one (index n / 2 - 1) and walking back to index 0.

Why is it faster? Half the nodes are leaves and need no work. A quarter can sink at most one row, an eighth at most two rows, and so on. Adding it up gives less than 2n swaps, so it is O(n).

class BuildHeap {
    // turn any array into a max heap in place, in O(n)
    static void buildMaxHeap(int[] a) {
        for (int i = a.length / 2 - 1; i >= 0; i--) {
            siftDown(a, a.length, i);
        }
    }

    static void siftDown(int[] a, int size, int i) {
        int left = 2 * i + 1, right = 2 * i + 2, big = i;
        if (left < size && a[left] > a[big]) big = left;
        if (right < size && a[right] > a[big]) big = right;
        if (big != i) {
            int t = a[i]; a[i] = a[big]; a[big] = t;
            siftDown(a, size, big);
        }
    }
}

Watch out for

• Sift down must pick the better of the two children, not the first one that beats the parent. Swapping with the smaller child in a max heap breaks the rule one row lower.
• Check right < size before reading the right child. The last parent may have only a left child.
• Use size, not a.length, once the array has spare room or after an extract.
• Comparing with a[i] - a[j] > 0 can overflow for big numbers. Compare with < and >.
• If indexes start at 1 instead of 0, the formulas change to 2i, 2i + 1 and i / 2. Do not mix the two styles.

What interviewers ask next

• How do you build a heap from n numbers in O(n)? Bottom up: sift down from index n / 2 - 1 back to 0, as shown above.
• How would you delete any item, not only the top? Swap it with the last item, shrink, then sift that spot both up and down. You need its index, so keep a map from item to index.
• How do you change a priority (decrease key)? Change the value, then sift up for a better value or sift down for a worse one.
• Why is the array not sorted? The rule is only parent against child. Brothers and cousins can be in any order, which is what makes the heap cheap to keep.
• How does Java do it? PriorityQueue is a min heap. Pass Collections.reverseOrder() for a max heap.

Remember this

Grown-up words: the pyramid is a complete binary tree, the rule is the heap property, climbing is sift up (heapify up), sinking is sift down (heapify down), the box that gives the biggest first is a priority queue, and pouring then fixing from the bottom is the bottom up build heap.