Heap Sort

Remember selection sort: find the biggest item, put it at the end, repeat. The plan is fine. The problem is the "find the biggest" part, which scans every remaining item every time. That scan is what makes it O(n²).

Now imagine the remaining items kept the biggest one at the front for you. After you take it, the next biggest rises to the front in a handful of moves. Selection sort would become fast. That arrangement is called a heap, and the sort that uses it is heap sort.

#A heap, in one minute

Picture the items as a family tree: one item at the top, and each item has at most two children below it. That shape is a binary tree. A max-heap is a binary tree where every parent is at least as big as its children. So the biggest item is always at the root. The full story is in Heaps and Priority Queues; heap sort needs only three facts:

• The tree is stored in a plain array, level by level. The children of index i are at 2i + 1 and 2i + 2. No pointers, no extra memory.
• The root, a[0], is the largest item.
• Sift down repairs a heap whose root is out of place: swap the item with its bigger child until it is at least as big as both children. The tree is about log₂ n levels tall, so that takes at most about log n swaps.

#The idea: two phases

1. Build a max-heap out of the whole array, in place.
2. Repeat: swap the root (the largest item) with the last item of the heap. That largest item is now in its final sorted position, so shrink the heap by one to leave it alone. The new root is probably small, so sift it down. Stop when the heap has one item left.

The array ends up split in two: a heap at the front that shrinks, and a sorted part at the back that grows. It is selection sort with a much faster way to find the maximum.

#Phase 1: build the heap

Items with no children (the second half of the array) are already tiny heaps of one. So start at the last item that has a child, at index n/2 − 1, and sift down each item from there back to the root. When you sift down an item, both of its subtrees are already heaps, so sifting it down makes its whole subtree a heap.

for i from n/2 - 1 down to 0: siftDown(a, i, n)for end from n - 1 down to 1:  swap a[0] and a[end]  siftDown(a, 0, end) siftDown(a, i, size):  while i has a child below size:    c = the bigger child of i    if a[c] <= a[i]: stop    swap a[i] and a[c]; i = c

#Phase 2: move the max to the end

Now the heap from the end of the last trace gets sorted. Faded tree nodes and green cells are the sorted part: they are no longer in the heap.

for i from n/2 - 1 down to 0: siftDown(a, i, n)for end from n - 1 down to 1:  swap a[0] and a[end]  siftDown(a, 0, end) siftDown(a, i, size):  while i has a child below size:    c = the bigger child of i    if a[c] <= a[i]: stop    swap a[i] and a[c]; i = c

#The code

function heapSort(a) {
  const n = a.length;
  // phase 1: build a max-heap, from the last parent up to the root
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);
  // phase 2: move the max to the end, shrink the heap, repair it
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end); // the heap is now a[0..end-1]
  }
  return a;
}
 
function siftDown(a, i, size) {
  while (true) {
    let big = i;
    const left = 2 * i + 1, right = 2 * i + 2;
    if (left < size && a[left] > a[big]) big = left;
    if (right < size && a[right] > a[big]) big = right;
    if (big === i) return; // bigger than both children: done
    [a[i], a[big]] = [a[big], a[i]];
    i = big;
  }
}
 
heapSort([3, 8, 5, 1, 9, 2]); // [1, 2, 3, 5, 8, 9]

def heap_sort(a):
    n = len(a)
    # phase 1: build a max-heap, from the last parent up to the root
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    # phase 2: move the max to the end, shrink the heap, repair it
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)  # the heap is now a[0..end-1]
    return a
 
def sift_down(a, i, size):
    while True:
        big = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[big]:
            big = left
        if right < size and a[right] > a[big]:
            big = right
        if big == i:  # bigger than both children: done
            return
        a[i], a[big] = a[big], a[i]
        i = big
 
heap_sort([3, 8, 5, 1, 9, 2])  # [1, 2, 3, 5, 8, 9]

#Cost

Phase 2 does n − 1 sift-downs, each at most log n levels deep: O(n log n). That holds for every input, because the heap is always about log n levels tall. There is no unlucky case like quicksort's bad pivots.

Phase 1 looks like it should also be O(n log n), but it is only O(n). Half of the items are leaves and never move. A quarter sit one level above the leaves and move at most one step. Only the root can travel the full height. Added up, that is fewer than n swaps.

Everything happens with swaps inside the array, so the extra space is O(1). That combination, a guaranteed O(n log n) with no extra memory, is what heap sort offers that neither merge sort nor quicksort does.

In practice, heap sort is usually slower than a good quicksort. Its sift-downs jump between distant parts of the array (index 1, then 3, then 7), which is unfriendly to the CPU cache. It is also not stable: the first swap of every round throws the root over everything in between.

#Common mistakes

#Check yourself

#What to practise next

Merge sort, quicksort and heap sort all sort by comparing items, and no comparison sort can beat O(n log n). Counting and Radix Sort get under that limit by not comparing at all, and that lesson ends with a table of every sort in this module.