Understanding Heap Sort

Heapsort is more complex than the sorting algorithms we have encountered so far, but it is clever, efficient, and very worth learning. The basic premise of heapsort is this:

Because of this, Heap Sort actually runs as quickly as merge sort, but without the added storage requirement!

What is a Heap?

A binary heap is a way to organize a list of numbers in such a way as to imitate a binary tree, where each number, or node of the tree, has up to two child nodes---one on the left, one on the right---and each child node is smaller than or equal to its parent node.

A Binary Tree

      7
  --5-|-6--
1-|-2   4-|-3

So how do we turn a list into a binary tree? Like this: we'll say that if the number b is the left child of the number a, then we'll make sure that the index of b in the array is equal to twice the index of a, and if it's the right child, we'll make its index be two times the index of a, plus one. This is actually the only rule we need to turn the above tree into a heap, so let's do it!

First, we make 7 the root, or first node, of the heap.

7

Then, we put its left child, 5, at index 2 * 1 = 2 (we're using 1-based indexing for now, so the index of 7 is 1).

7 5

And the right child of 7, which is 6, can go at position 2 * 1 + 1 = 3.

7 5 6

Next, we look at the children of 5. Its left child is 1, which goes to 2 * 2 = 4, and its right child is 2, which goes to 2 * 2 + 1 = 5.

7 5 6 1 2

Finally, the children of 6, which are 4 and 3, go to positions 2 * 3 = 6 and 2 * 3 + 1 = 7, respectively.

7 5 6 1 2 4 3

And that's our binary heap! Notice that, although the array is out of order, it still maintains the heap property---no element is larger than its parent. It follows from where we put our child elements that the parent of the element at i is the element at i / 2, rounded down, so you can test this out for yourself.

Getting Started

The first thing we'll need is some functions to locate the child elements of a given element (remember, this just means multiplying its index by 2 to find its left child, and multiplying by 2 and adding 1 to find its right child).

int LEFT(int i) {
    // return the index of the left child of a node
    return i * 2;
}

int RIGHT(int i) {
    // return the index of the right child of a node
    return i * 2 + 1;
}

Now that we have a way to find the children of a node, we can start writing functions.

The 'Heapify' Function

"Heapify" is the most important function in heapsort. It takes an index in a heap, and moves that element around until it obeys the heap property; that is, until it is not larger than its parent element. It's a pretty simple process. If we call heapify on the element e at index i, it will look at e's children. If either the left or right child of e is greater than it, heapify will exchange e with the greater of the two. After doing that, it will call heapify again, on the index where e ended up! This ensures that e will continue to be heapifyed until neither of its children is larger than it.

Let's write this in C.

void heapify(int heap_size, long * inputv, int i) {
    /** This function moves the element at i to 
     *  a position where it is not greater than
     *  either of its children **/

    int l = LEFT(i);
    int r = RIGHT(i);

    int largest;
    if ( l < heap_size && inputv[l] > inputv[i]) largest = l;
    else largest = i;
    // set the greater of the current and the left index as largest

    if ( r < heap_size && inputv[r] > inputv[largest] ) largest = r;
    // if the right index is larger, set it as the largest

    if (largest != i) {
        // if current index is not largest
        // swap largest and current
        long tmp = inputv[i];
        inputv[i] = inputv[largest];
        inputv[largest] = tmp;

        // repeat the whole process; note that heapify is called with
        // the index that the original element ended up at
        heapify(heap_size, inputv, largest);
    }
}

We can set up a way to test this code, using some code I wrote to run sorting algorithms on command line input:

#include "../clilonglist.h" // my command-line input utility functions
#include <stdlib.h>

...

void heapify(int heap_size, long * inputv, int i) {
    ...
}

int main(int argc, char * argv[]) {

    int inputc = argc - 1;
    long * inputv = extract_long_list(inputc, argv);
    // use my utility functions to grab the 
    // command line arguments as an array of longs
    
    heapify(inputc, inputv, 0);
    print_long_list(inputc, inputv);

    free(inputv);
}

Let's run heapify!

• ./heapify 1 5 3 5 3 1

When we take 1 3 5 and tell our program to heapify index 0, the computer tries to put the 1 in a spot where it isn't smaller than any of its children. It compares it with its children, the 5 and the 3, notices that the 5 is the largest of the three, and switches the 1 and the 5, leaving us with a valid heap. If the 1 had ended up in a spot where one of its children was still larger than it, heapify would simply call itself again! Effectively, heapify takes a heap with one item out of place, and turns it into a valid heap. This will come in handy!

Turning a List into a Heap

To perform a heapsort, we'll need to be able to re-order a list into a heap. It turns out that our heapify function is all we need to do that. Remember---heapify takes a heap with one misplaced element and makes it valid. So, if we have a valid heap and we stick an extra element in front of it, we can treat both the heap and the extra element as the same structure: a heap, but with the first item in the wrong place. If we then call heapify on index 0 of that larger heap, it will put the new item in a valid location, leaving us with a valid heap!

So, to create a build_heap function, we just need to loop through the array from right to left, using heapify to transform it into a heap as we go along. In fact, only the nodes in the first half of a heap will have child nodes, so we don't even need to call heapify on the second half of the array. Let's write some code.

void build_heap(int inputc, long * inputv) {
    /** This function turns a simple array into 
     *  a heap by calling heapify() repeatedly. **/

    for ( int i = (inputc + 1) / 2; i >= 0; i--) {
        heapify(inputc, inputv, i);
    }
}

Let's try this out on a list.

• ./build_heap 3 5 1 2 8 7 9 0 9 8 7 5 1 3 2 0

That worked! Notice that all we did was reorder the array to ensure that no child was larger than its parent. That's basically what a heap is---a list that obeys the heap property.

Now that we can turn a list into a heap, all we need to do is learn how to sort a heap, and then we'll be able to sort lists, by turning them into heaps first!

Sorting Heaps

I claim that the heap is a structure that is intrinsically easy to sort. Let's go through it in our heads. We know that the largest element in the heap is always going to be the one in the first position. That part is easy, then---we just take the first element of our heap, and make it the last element of our sorted list. But then, we run into a problem. Once we've taken away the first element, we have no guarantee that the new first element---the element that used to be the left child of the first element---is the largest element remaining. Remember, all that is guaranteed is that child nodes are not greater than their parents, so there's no guarantee that a left child is greater than its corresponding right child, so our heap is now messed up.

We can make this better, though. Where do we want the largest element to end up in the sorted list? At the end, obviously. So, instead of taking the largest element from our list and putting it in a new separate array, let's just put it at the end of our heap array. There's already an element in that position, so let's just switch the two. We no longer consider the largest element to be part of the heap, so instead of having a heap with the first item missing, we have a heap with the last item missing, and a possibly invalid first item---actually a much better situation!

A heap with the last item missing is still a valid heap, so we don't need to worry about that. What we do need to worry about is the new first item in the heap---it used to be the last item, so it's probably smaller than its children now. But, remember what we said earlier?

That's what we have now! A heap with the first item out of place. So all we need to do is call heapify on the first index of our heap, and then we'll have a valid heap again. Once there, we can repeat the whole process, because the new first element is guaranteed to be the largest. One by one, we'll use heapify to make sure the largest element is first, and then we'll take it and put it into our sorted list, by switching it with the last item of the slowly shrinking heap. Once the heap shrinks to nothing, we'll have a sorted list!

Let's look at the code for heap_sort.

void heap_sort(int inputc, long * inputv) {
    /** This function sorts inputv
     *  by first turning it into a
     *  heap, and then removing the
     *  largest elements from the 
     *  heap one by one **/

    build_heap(inputc, inputv);

    for ( int i = inputc - 1; i >= 1; i--) {
        // starting from the end of the list

        // switch the ith element with the first
        long tmp = inputv[i];
        inputv[i] = inputv[0];
        inputv[0] = tmp;
        // this puts the largest element (the one
        // at index 0) at the end of the array

        // re-heapify the part of the array UP TO
        // THE LARGEST VALUE THAT WE JUST MOVED,
        // so that the first section of the array
        // is a shrinking heap, but the second 
        // section is a growing sorted list.
        heapify(i, inputv, 0);
    }

}

This function is hard to wrap your head around, but it's fundamentally just a for loop in reverse, a swap, and a heapify. Put it together with the rest of our code:

#include "../clilonglist.h" // my command-line input utility functions
#include <stdlib.h>

...

void heapify(int heap_size, long * inputv, int i) {
    ...
}

void build_heap(int inputc, long * inputv) {
    ...
}

void heap_sort(int inputc, long * inputv) {
    ...
}

int main(int argc, char * argv[]) {

    int inputc = argc - 1;
    long * inputv = extract_long_list(inputc, argv);
    // use my utility functions to grab the 
    // command line arguments as an array of longs
    
    heap_sort(inputc, inputv);
    print_long_list(inputc, inputv);

    free(inputv);
}

Let's run our finalized sorting algorithm!

• ./heap_sort 3 5 1 2 8 7 9 0 0 1 2 3 5 7 8 9

Sorted! Very nice.

Conclusion

The key to heapsort is the heapify function. Once we have that, we can use it repeatedly to build a heap with the build_heap function, and use it to continually ensure that the largest element is always first in our heap as we turn it into a sorted list with our heap_sort function. As always, all code is on Github. Good luck!