Interview Cake
An unsorted input [2, 4, 7, 8, 1, 3, 6] is transformed into a binary heap (8; 2, 7; 4, 1, 3, 6) which is used to create the sorted output [1, 2, 3, 4, 6, 7, 8].

Heapsort Algorithm

Sorting Algorithm

Quick reference

Complexity
Worst case time
Best case time
Average case time
Space

Strengths:

  • Fast. Heap sort runs in time, which scales well as n grows. Unlike quicksort, there's no worst-case complexity.
  • Space efficient. Heap sort takes space. That's way better than merge sort's overhead.

Weaknesses:

  • Slow in practice. While the asymptotic complexity of heap sort makes it look faster than quicksort, in real systems heap sort is often slower. (Remember, n and 2n are both , even though the first is twice as fast as the second. Heap sort's hides constant factors, but they still impact overall performance.)

The High-Level Idea

Heapsort is similar to selection sort—we're repeatedly choosing the largest item and moving it to the end of our list. The main difference is that instead of scanning through the entire list to find the largest item, we convert the list into a max heap to speed things up.

Heapify

Our first step is to transform the input list into a heap (a.k.a. "heapify" it).

Take this example input:

An unsorted input [8, 3, 2, 7, 9, 1, 4].

Instead of treating the input like a list, we can treat it like the nodes in a complete binary tree. The 0^{th} item in the list is the root; the 1^{st} item in the list is the root's left child, and so on.

The list [8, 3, 2, 7, 9, 1, 4] maps to a complete binary tree (8; 3, 2; 7, 9, 1, 4). Nodes within a level are separated by a comma; levels are separated with semicolons.

We're not actually creating a tree here. We're just treating the input like it specifies the nodes in a tree.

When we manipulate the tree by moving around items or removing elements, we're actually rearranging the underlying input list (not some separate tree structure).

We'll show both the tree and the list in our diagrams, but the tree is just to help us visualize how we're interpreting the list as a heap. In memory, we're just storing the list.

Our tree will need some fixups in order to make it into a valid heap. For instance, it's definitely not valid now since the largest element (9) isn't at the root.

To transform the tree into a heap, we'll work from the bottom of the tree upwards. We'll compare each node to its children and move nodes around so that parent nodes are always larger than their children.

This causes smaller nodes to move lower in the tree, "bubbling down" to allow larger values to reach the top.

To start off, let's look at the leaves.

The leaf nodes don't have any children, so they don't need to move down at all. Great.

In the binary tree (8; 3, 2; 7, 9, 1, 4), the bottom 4 nodes (7, 9, 1, 4) correspond to the last four elements in the list [8, 3, 2, 7, 9, 1, 4].

Let's look at the nodes in the next level:

In the binary tree (8; 3, 2,; 7, 9, 1, 4), the middle level has two nodes (3, 2), which correspond to the second and third elements in the list [8, 3, 2, 7, 9, 1, 4].

We'll start with the left node (3) and its children:

The (3) node has two children: 7 and 9. In the list [8, 3, 2, 7, 9, 1, 4], node (3) is at index 1 and its children are at indices 3 and 4.

Since 7 and 9 are both greater than 3, we definitely need to move some items around. We'll swap the 3 and the 9 to make the parent larger than its children. (If we'd swapped the 3 with the 7, then we'd still have a problem since the parent node (7) would be smaller than one of its children (9).)

In the tree, the (3) is swapped with its larger child (9). In the list, this means swapping the elements at index 1 and 4. The resulting tree is (8; 9, 2; 7, 3, 1, 4).

Next we'll look at the right node (2) and its children. Since 4 is larger than 2, we'll swap them.

In the tree, the (2) is swapped with its larger child (4). In the list, this means swapping the elements at index 2 and 6. The resulting tree is (8; 9, 4; 7, 3, 1, 2).

Notice how we've got two small valid max-heaps. We're getting close!

Within the tree (8; 9, 4; 7, 3, 1, 2), we have two valid max heaps: (9; 7, 3) and (4; 1, 2).

Moving up, we've got an 8 at the root.

At this point, our tree is (8; 9, 4; 7, 3, 1, 2). The root node, (8), is at index 0 of our list: [8, 9, 4, 7, 3, 1, 2].

Since 8 is smaller than 9, 8 bubbles down, swapping places with the larger child: 9.

(8) is swapped with its larger child (9) in the tree. This corresponds to swapping the elements at index 0 and 1 in the list. The result is (9; 8, 4; 7, 3, 1, 2).

Then, we need to compare 8 to its two children—7 and 3. Since 8 is bigger than both of them, we're done bubbling down and don't need to do any additional swaps.

At this point, we've transformed the input tree into a valid max heap. Nice!

Repeatedly Removing The Max

Each time we remove an element from the heap, it's the largest item in the underlying list. So, in sorted order, it belongs at the end of the list. As we'll see, removing an item from the heap conveniently frees up space at the end of the underlying list where we can put the removed item.

Here's what that looks like. Taking our heap from earlier:

Our heap is (9; 8, 4; 7, 3, 1, 2).

We'll remove the max element.

Removing (9), we have a hole at the root of our heap: (_; 8, 4; 7, 3, 1, 2). Our list has a similar hole at the 0th index: [_, 8, 4, 7, 3, 1, 2].

That leaves a gap at the root that needs to be filled. We'll put our right-most item (2) there.

(2) moves from the bottom-right of the heap to the root. The result is (2; 8, 4; 7, 3, 1). Our list becomes [2, 8, 4, 7, 3, 1, _].

But this isn't a valid heap anymore. Our largest item (8) isn't at the root. So we'll "bubble down" to restore our heap (just like in our heapify step).

(2) is swapped with its larger child (8), resulting in (8; 2, 4; 7, 3, 1) (as a heap) or [8, 2, 4, 7, 3, 1, _] (as a list). The process repeats for the next level, and (2) is swapped with its larger child (7). The final result is (8; 7, 4; 2, 3, 1) (as a heap) or [8, 7, 4, 2, 3, 1, _] (as a list).

Notice the empty hole at the end of the list? We'll fill that in with the 9 we removed.

The hole at the end the list is filled with the old root element (9). The resulting list is [8, 7, 4, 2, 3, 1, 9].

We've got the largest item at the end of the list. Progress! We'll continue this strategy, removing the next largest item from our heap and adding it to our growing sorted section at the end of the list.

The list [8, 7, 4, 2, 3, 1, 9] can be broken into an unsorted portion [8, 7, 4, 2, 3, 1] and a sorted portion [9].

The next-largest element is 8. We'll remove it from the root, filling its spot with the bottom, right-most element (1).

Removing the (8) and replacing it with the bottom right element (1), our heap becomes (1; 7, 4; 2, 3), which is [1, 7, 4, 2, 3, _, 9] as a list.

To finish up the removal, we have to bubble down the 1 to make the heap valid again.

(1) bubbles down, swapping with (7), which creates (7; 1, 4; 2, 3) (as a heap) or [7, 1, 4, 2, 3, _, 9] (as a list). The process repeats for the next level, and (1) is swapped with (3) to create (7; 3, 4; 2, 1) (as a heap). As a list, we have [7, 3, 4, 2, 1, _, 9].

Finally, we can use the freed space where the 1 used to be to store the removed max value (8).

The hole in the list is filled in with the old root element (8). The resulting list is [7, 3, 4, 2, 1, 8, 9]. The last two elements [8, 9] are sorted; the remainder is unsorted.

Removing the next-largest value (7), we've got:

(7) is removed and replaced with the bottom-right most value (1). The resulting heap is (1; 3, 4; 2); the resulting list is [1, 3, 4, 2, _, 8, 9].

And after "bubbling down":

After (1) is bubbled down, the heap becomes (4; 3, 1; 2). (7) fills in the hole in the list made by moving (1), resulting in [4, 3, 1, 2, 7, 8, 9].

Next up, 4:

(4) is removed and replaced with the bottom-right most value (2). The resulting heap is (2; 3, 1); the resulting list is [2, 3, 1, _, 7, 8, 9].

And after "bubbling down":

After (2) is bubbled down, the heap becomes (3; 2, 1). (4) fills in the hole in the list made by moving (2), resulting in [3, 2, 1, 4, 7, 8, 9].

You can probably finish the rest yourself. :)

Implementation

Here's how we'd code it up:

def left_child_index(parent_index): return parent_index * 2 + 1 def right_child_index(parent_index): return parent_index * 2 + 2 def bubble_down(heap, heap_length, index): ''' Restore a max heap where the value at index may be out of place (i.e.: smaller than its children). ''' while index < heap_length: left_index = left_child_index(index) right_index = right_child_index(index) # If we don't have any child nodes, we can stop if left_index >= heap_length: break # Find the larger of the two children larger_child_index = left_index if right_index < heap_length and heap[left_index] < heap[right_index]: larger_child_index = right_index # Are we larger than our children? # If so, swap with the larger child. if heap[index] < heap[larger_child_index]: heap[index], heap[larger_child_index] = heap[larger_child_index], heap[index] # Continue bubbling down index = larger_child_index else: # We're larger than both children, so we're done break def remove_max(heap, heap_length): ''' Remove and return the largest item from a heap. Updates the heap in-place, maintaining validity. ''' # Grab the largest value from the root max_value = heap[0] # Move the last item in the heap into the root position heap[0] = heap[heap_length - 1] # And bubble down from the root to restore the heap bubble_down(heap, heap_length - 1, 0) return max_value def heapify(the_list): # Bubble down from the leaf nodes up to the top for index in xrange(len(the_list) - 1, -1, -1): bubble_down(the_list, len(the_list), index) def heapsort(the_list): heapify(the_list) heap_size = len(the_list) while heap_size > 0: # Remove the largest item and update the heap size largest_value = remove_max(the_list, heap_size) heap_size -= 1 # Store the removed value at the end of the list, after # the entries used by the heap the_list[heap_size] = largest_value

Complexity

For the heapify step, we're examining every item in the tree and moving it downwards until it's larger than its children. Since our tree height is , we could do up to moves. Across all n nodes, that's an overall time complexity of .

We've shown that the heapify step is . With a bit more complex analysis, it turns out to actually be . Pretty cool!

After transforming the tree into a heap, we remove all n elements from it—one item at a time. Removing from a heap takes time, since we have to move a new value to the root of the heap and bubble down. Doing n remove operations will be time.

Is this analysis too pessimistic? Each time we remove an item from the heap it gets smaller, so won't later removes be cheaper than earlier ones?

A more thorough analysis shows that doing n removals is still .

Putting these steps together, we're at time in the worst case (and on average).

But what happens if all the items in the input are the same?

Every time we remove an element from the tree root, the item replacing it won't have to bubble down at all. In that case, each remove takes time, and doing n remove operations takes .

So the best case time complexity is . This is the runtime when everything in the input is identical.

Since we cleverly reused available space at the end of the input list to store the item we removed, we only need space overall for heapsort.

What's next?

If you're ready to start applying these concepts to some problems, check out our mock coding interview questions.

They mimic a real interview by offering hints when you're stuck or you're missing an optimization.

Try some questions now

. . .