Heap algorithm design

**Heap sort** builds a **max-heap** from the array in O(n), then repeatedly swaps the root (the maximum) with the last element of the heap, shrinks the heap by one and sifts the new root down. The sorted part grows at the end of the array, so the sort is **in place** and takes O(n log n) in every case, with O(1) extra memory. It is **not stable**, and its access pattern jumps around memory, so quick sort and merge sort are usually faster in practice.

In the “Unsorted” preset the animation sorts with 27 comparisons and 20 swaps; the “Duplicates” preset shows equal keys passing each other, which is why the sort is not stable.

1static void heapSort(int[] a) {
2    int n = a.length;
3    for (int i = n / 2 - 1; i >= 0; i--) siftDownMax(a, n, i);   // build a max-heap in O(n)
4    for (int end = n - 1; end > 0; end--) {
5        swap(a, 0, end);                         // the maximum goes to its final place
6        siftDownMax(a, end, 0);                  // restore the heap in the shorter prefix
7    }
8}
9static void siftDownMax(int[] a, int n, int i) {
10    while (true) {
11        int l = 2 * i + 1, r = l + 1, m = i;
12        if (l < n && a[l] > a[m]) m = l;
13        if (r < n && a[r] > a[m]) m = r;
14        if (m == i) return;
15        swap(a, i, m);
16        i = m;
17    }
18}

1public static void heapSort(int[] arr) {
2    int n = arr.length;
3    for (int i = n / 2 - 1; i >= 0; i--) {
4        siftDown(arr, n, i);                 // build a max-heap
5    }
6    for (int end = n - 1; end > 0; end--) {
7        swap(arr, 0, end);                   // largest goes to its final slot
8        siftDown(arr, end, 0);               // repair the smaller heap
9    }
10}
11
12static void siftDown(int[] arr, int size, int i) {
13    while (true) {
14        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
15        if (l < size && arr[l] > arr[largest]) largest = l;
16        if (r < size && arr[r] > arr[largest]) largest = r;
17        if (largest == i) return;
18        swap(arr, i, largest);
19        i = largest;
20    }
21}

To find the **k largest** of n items without sorting them all, keep a **min-heap of size k**. For each item: if the heap has fewer than k items, add it; otherwise, if the item is larger than the root (the smallest of the current k), replace the root with it. At the end the heap holds the k largest. The cost is O(n log k) time and O(k) space, far better than sorting when k is small, and it works on a stream that does not fit in memory.

The “K = 3” preset keeps 20, 17 and 14 with 15 comparisons. The input order matters for the cost: the “Increasing stream” preset replaces the root almost every time (17 comparisons) while the “Decreasing stream” preset never does after the first 3 items (7 comparisons).

1static int[] topK(int[] a, int k) {              // the k largest values, in descending order
2    PriorityQueue<Integer> heap = new PriorityQueue<>();      // min-heap: the root is the smallest of the k kept
3    for (int x : a) {
4        if (heap.size() < k) heap.add(x);
5        else if (x > heap.peek()) { heap.poll(); heap.add(x); }
6    }
7    int[] out = new int[heap.size()];
8    for (int i = out.length - 1; i >= 0; i--) out[i] = heap.poll();
9    return out;
10}

1public static int[] topK(int[] nums, int k) {
2    PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap
3    for (int x : nums) {
4        if (heap.size() < k) {
5            heap.add(x);
6        } else if (x > heap.peek()) {
7            heap.poll();
8            heap.add(x);
9        }
10    }
11    return heap.stream().mapToInt(i -> i).toArray();
12}

'What is the k-th largest value so far?' over a stream is the same structure: a min-heap that holds the k largest values seen, whose **root is the answer**. Each new value costs O(log k), and the query is O(1). It never needs the values that fell out of the top k.

Until k values have arrived there is no k-th largest; define what to return (here, null) rather than letting the code fail on an empty heap.

1static class KthLargest {
2    private final int k;
3    private final PriorityQueue<Integer> heap = new PriorityQueue<>();   // the k largest values seen
4    KthLargest(int k) { this.k = k; }
5    Integer add(int x) {                         // returns the k-th largest so far, or null if fewer than k values
6        if (heap.size() < k) heap.add(x);
7        else if (x > heap.peek()) { heap.poll(); heap.add(x); }
8        return heap.size() < k ? null : heap.peek();
9    }
10}

1public static int[] topK(int[] nums, int k) {
2    PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap
3    for (int x : nums) {
4        if (heap.size() < k) {
5            heap.add(x);
6        } else if (x > heap.peek()) {
7            heap.poll();
8            heap.add(x);
9        }
10    }
11    return heap.stream().mapToInt(i -> i).toArray();
12}

To merge k sorted sequences, keep a min-heap of their **current heads**, one entry per sequence: repeatedly remove the smallest, output it, and push the next element of the sequence it came from. The heap never holds more than k entries, so each of the n outputs costs O(log k), for O(n log k) in all, compared with O(n · k) for scanning all k heads each time.

In the animation the “3 runs” preset merges 9 values with 15 comparisons of run heads and the “2 runs” preset needs only 8, because it scans the heads directly; a heap replaces that O(k) scan by an O(log k) step, which matters for large k. This is also the merge step of external sorting, where each run is a sorted file too large for memory.

1static List<Integer> mergeK(int[][] lists) {
2    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));   // {value, list, index}
3    for (int i = 0; i < lists.length; i++) if (lists[i].length > 0) heap.add(new int[]{lists[i][0], i, 0});
4    List<Integer> out = new ArrayList<>();
5    while (!heap.isEmpty()) {
6        int[] top = heap.poll();                 // the smallest head
7        out.add(top[0]);
8        int next = top[2] + 1;
9        if (next < lists[top[1]].length) heap.add(new int[]{lists[top[1]][next], top[1], next});
10    }
11    return out;
12}

1public static int[] kWayMerge(int[][] runs) {
2    int k = runs.length, total = 0;
3    for (int[] r : runs) total += r.length;
4    int[] pos = new int[k];                // next unread index in each run
5    int[] out = new int[total];
6    for (int o = 0; o < total; o++) {
7        int best = -1;
8        for (int r = 0; r < k; r++) {
9            if (pos[r] < runs[r].length &&
10                (best == -1 || runs[r][pos[r]] < runs[best][pos[best]])) {
11                best = r;
12            }
13        }
14        out[o] = runs[best][pos[best]++];
15    }
16    return out;
17}