Heap and heap sort in Java

Problem

The top 10 out of one million

The shop has a million products and knows how many times each one was sold. The home page needs the top 10 by sales. This is computed every time the page opens.

The first thing that comes to mind is to sort them all and take the first 10. Merge sort makes about 18.7 million comparisons for a million products (see merge sort). You need 10 rows of it. The other 999,990 products are sorted for nothing.

There is a second pain too. Quick sort sorts in place, but with a bad pivot it falls to O(n²) (see quick sort). Merge sort is O(n log n) every time, but it needs a second array as big as the first. Can you have both: in place and O(n log n) every time?

The idea

A heap: a tree stored in an array

Both need a structure that knows one thing only: which one is the biggest. Everything does not have to be sorted.

Draw the array as a tree. Index 0 is the top. Under every index i there are two children:

the left child is at 2i + 1;
the right child is at 2i + 2;
the parent of index i is at (i - 1) / 2, with integer division.

There are no pointers. The tree is just a way of looking at the array.

The array is a heap (a max-heap, to be precise) when every parent is at least as big as its children. Then the biggest is always at index 0. That is the only order there is: siblings can be in any order between themselves.

See it

The children and the parent by index

A heap of seven sales. The program walks over the parents and prints their children, then finds the parent of index 4:

int[] heap = {58, 40, 25, 31, 12, 3, 7};
for (int i = 0; 2 * i + 2 < heap.length; i++) {
    int left = 2 * i + 1, right = 2 * i + 2;
    System.out.println(heap[i] + " -> " + heap[left] + " " + heap[right]);
}
int child = 4;
int parent = (child - 1) / 2;
System.out.println("the parent of " + heap[child] + " (index " + child + ") is " + heap[parent] + " (index " + parent + ")");

58 -> 40 25
40 -> 31 12
25 -> 3 7
the parent of 12 (index 4) is 40 (index 1)

58 is above 40 and 25, 40 is above 31 and 12, 25 is above 3 and 7. Every parent is bigger than its children, and 58 is the biggest.

(child - 1) / 2 is division of whole numbers: 3 / 2 is 1, the remainder is dropped.

See it

Sinking: how an array becomes a heap

How does an array in any order become a heap? With one operation: sinking (sift down). The element at index i is compared with its two children. If one of them is bigger, it swaps places with the bigger one, and the element goes on down. It stops when it is at least as big as its children or when there are no children.

The build runs the sinking for every parent, from the last one to the top. The leaves (the bottom row) have no children: each of them is a heap on its own. So when you reach a parent, the two subtrees under it are already heaps, and it only has to sink to its place.

static void siftDown(int[] a, int i, int n) {
    while (true) {
        int big = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && a[left] > a[big]) big = left;
        if (right < n && a[right] > a[big]) big = right;
        if (big == i) return;
        swap(a, i, big);
        i = big;
    }
}

Heap sort is the build plus one more loop. The maximum is at index 0: it swaps with the last element and is now in its final place. The heap shrinks by one, and the new top sinks. That happens n - 1 times:

static void buildHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        siftDown(a, i, a.length);
    }
}

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end);
    }
}

int[] sales = {12, 40, 7, 31, 58, 3, 25};
buildHeap(sales);
System.out.println("Heap: " + Arrays.toString(sales));
heapSort(sales);
System.out.println("Sorted: " + Arrays.toString(sales));

Heap: [58, 40, 25, 31, 12, 3, 7]
Sorted: [3, 7, 12, 25, 31, 40, 58]

static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

static void siftDown(int[] a, int i, int n) {
    while (true) {
        int big = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && a[left] > a[big]) big = left;
        if (right < n && a[right] > a[big]) big = right;
        if (big == i) return;
        swap(a, i, big);
        i = big;
    }
}

static void buildHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        siftDown(a, i, a.length);
    }
}

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end);
    }
}

Step by step, in words

Seven sales in an array. The same array is a tree: the children of index i are at 2i + 1 and 2i + 2.
The build starts from the last parent, index 2. siftDown: 7 is smaller than its child 25, so they swap.
Index 1: 40 against 31 and 58. The bigger child is 58: swap.
The root: 12 swaps with 58, then keeps sinking. One level down 40 is bigger: one more swap.
A heap: every parent is at least as big as its children. The maximum, 58, is at index 0.
Heap sort: the maximum swaps with the last element. 58 is in its final place, and the heap shrinks to six.
The new root, 7, sinks: swap with 40, then with 31. Now the top is 40, the next maximum. That repeats n - 1 times.

There is no second array: the swaps happen in the array itself. That is sorting in place.

Try it

Predict the output

The build runs the sinking from the last parent to the top. What is in the array after it?

int[] sales = {5, 9, 2, 8};
buildHeap(sales);
System.out.println(Arrays.toString(sales));

Answer

[9, 8, 2, 5]

[9, 5, 2, 8]

[2, 5, 8, 9]

Try it

Fill in

The left child of index i is:

int left = , right = 2 * i + 2;

The idea

What it costs

Sinking: on every level two comparisons and at most one swap. A tree of n elements has about log₂ n levels, so sinking is O(log n).
Building: it looks like n sinkings of log n each, but it is O(n). Half of the elements are leaves and do not sink at all, a quarter go down at most one level, an eighth two… The sum is under 2n.
Heap sort: the build plus n - 1 sinkings from the top: O(n log n) in every case. There is no bad input, like a bad pivot in quick sort.

Run it against merge sort. Both count their comparisons:

Heap sort O(n log n)
Sorting (merge sort) O(n log n)

Algorithm	n = 10	n = 1,000	n = 100,000
Heap sort	38	16,807	3,019,656
Sorting (merge sort)	21	8,709	1,536,371

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

static void siftDown(int[] a, int i, int n) {
    while (true) {
        int big = i;
        int left = 2 * i + 1, right = 2 * i + 2;
        if (left < n && a[left] > a[big]) big = left;
        if (right < n && a[right] > a[big]) big = right;
        if (big == i) return;
        swap(a, i, big);
        i = big;
    }
}

static void buildHeap(int[] a) {
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        siftDown(a, i, a.length);
    }
}

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end);
    }
}

The two curves grow the same way, but heap sort makes about twice as many comparisons: for 100,000 sales 3,019,656 against 1,536,371. Every sinking from the top goes almost to the bottom, because a small element was put there.

There is a second thing the count does not show: memory. From index i the sinking jumps to 2i + 1. In a big array that is far away, and every time the processor waits for another piece of memory to arrive. Merge sort and quick sort read in order, and that is exactly when the processor is fast. So in practice heap sort is slower, even though it promises O(n log n) every time.

More precisely, if you are curious

Why is the built-in sort not heap sort? Because of the above. Heap sort is the fallback: in C# Array.Sort is introsort, which starts with quick sort and switches to heap sort if the partitioning gets too deep. That way it keeps O(n log n) without paying the price of heap sort every time. Heap sort is not stable either: two products with equal sales can swap their order. What that means is in the lesson on stability.

Why the build is O(n): at height h from the bottom there are about n / 2ʰ⁺¹ elements, and each goes down at most h levels. The sum n · (1/4 + 2/8 + 3/16 + …) is n · 1 = n.

Try it

Find the bug

Someone wrote heap sort, but the sorted result comes out scrambled:

static void heapSort(int[] a) {
    buildHeap(a);
    for (int end = a.length - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, a.length);
    }
}

int[] sales = {12, 40, 7, 31, 58, 3, 25};
heapSort(sales);
System.out.println(Arrays.toString(sales));

[58, 31, 40, 25, 12, 7, 3]

Which line is the bug on?

Pick the line with the bug.

See it

The top 10 without sorting everything

Back to the home page. Turn the idea around: keep a min-heap of 10 elements, with the smallest of them at the top. It is the "tenth": the bar a product has to be above to get in.

While there are fewer than 10, every product gets in.
After that, every new one is compared with the top only. If it is bigger, it takes the place of the top and sinks. If not, it drops out after one comparison.

In Java PriorityQueue is exactly such a min-heap: peek() gives the top, poll() takes it out, add() adds and floats up.

record Product(int id, int sold) {}

PriorityQueue<Product> best = new PriorityQueue<>(Comparator.comparingInt(Product::sold));
for (int id = 1; id <= 1_000_000; id++) {
    Product p = new Product(id, (int) (id * 48271L % 1_000_003));
    if (best.size() < 10) {
        best.add(p);
    } else if (p.sold() > best.peek().sold()) {
        best.poll();
        best.add(p);
    }
}
List<Product> top = new ArrayList<>(best);
top.sort(Comparator.comparingInt(Product::sold).reversed());
for (Product p : top) {
    System.out.println("product " + p.id() + ": " + p.sold() + " sold");
}

product 188706: 1000002 sold
product 377412: 1000001 sold
product 566118: 1000000 sold
product 754824: 999999 sold
product 943530: 999998 sold
product 132233: 999997 sold
product 320939: 999996 sold
product 509645: 999995 sold
product 698351: 999994 sold
product 887057: 999993 sold

Run it against sorting everything, up to one million:

The top 10 with a heap O(n)
Sorting (merge sort) O(n log n)

Algorithm	n = 10	n = 1,000	n = 100,000	n = 1,000,000
The top 10 with a heap	15	1,177	100,410	1,000,467
Sorting (merge sort)	21	8,709	1,536,371	18,674,993

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

For a million products the heap makes 1,000,467 comparisons, and merge sort 18,674,993. The work is O(n · log 10): the heap never grows past 10, so there is almost exactly one comparison per product.

More precisely, if you are curious

A heap you take "the most important one" out of and add new ones to is a priority queue. It is a topic of its own in the module "Data structures": that is where floating up is, and why tasks in a scheduler, events in a simulation and Dijkstra all sit on top of it.

PriorityQueue in Java is a min-heap by natural order. For a max-heap you pass Comparator.reverseOrder().

How it is in the other languages: Java has PriorityQueue, C# PriorityQueue<TElement, TPriority>, Python heapq, and JavaScript has no built-in heap.

Exercise

The top three

Solve the task in your editor.

The top three by sales. The sales of twelve products are 12, 40, 7, 31, 58, 3, 25, 44, 19, 36, 50, 8. Find the three biggest with a min-heap that never has more than three elements, and print them from the biggest.

The top three: [58, 50, 44]

More tasks

A min-heap by hand. Rewrite siftDown so that a parent is at most as big as its children. Sort the sales in reverse order with it.
Counting the comparisons. Add a counter to the sinking and run heap sort on 7, 1000 and 100,000 sales. Does it grow like n log n?
The bottom 10. Which 10 products sell the worst? What kind of heap do you need now?

Test

Check yourself

1. A heap is stored in an array. The top is at index 0. Where are the children of index 3?At 6 and 7At 7 and 8At 4 and 5

2. What does a max-heap guarantee?The left child is smaller than the right oneThe array is sortedEvery parent is at least as big as its children, so the maximum is at index 0

3. You need the top 10 by sales out of a million products. What does the least work?Keep a min-heap of 10 elements and compare each new one with its topSort them all and take the first 10Look for the maximum in the whole list ten times

4. Heap sort is O(n log n) every time and needs no extra memory. Why is the built-in sort not heap sort?Because it only works with whole numbersIt makes about twice as many comparisons as merge sort and jumps around memory, while the processor likes to read in orderBecause it is O(n²) in the worst case

Heap and heap sort

Cookies