An intuitive understanding of heapsort?

Question

At school we are currently learning sorting algorithms in Java and I got for my homework the Heap Sort. I did my reading, I tried to find out as much as I could, but it seems I just can't grasp the concept.

I'm not asking you to write me a Java program, if you could just explain to me as simply as you can how the Heap Sort works.

Answer 1

Right, so basically you take a heap and pull out the first node in the heap - as the first node is guaranteed to be the largest / smallest depending on the direction of sort. The tricky thing is re-balancing / creating the heap in the first place.

Two steps were required for me to understand the heap process - first of all thinking of this as a tree, getting my head around it, then turning that tree into an array so it could be useful.

The second part of that is to essentially traverse the tree breadth first, left to right adding each element into the array. So the following tree:

                                    73                                                            7      12                                          2   4  9   10                                  1           

Would be {73,7,12,2,4,9,10,1}

The first part requires two steps:

1. Make sure each node has two children (Unless you don't have enough nodes to do that as in the tree above.
2. Make sure each node is bigger (Or smaller if sorting min first) than its children.

So to heapify a list of numbers you add each one to the heap, then following those two steps in order.

To create my heap above I will add 10 first - it's the only node so nothing to do. Add 12 as it's child on the left:

    10   12 

This satisfies 1, but not 2 so I will swap them round:

    12   10 

Add 7 - nothing to do

    12   10  7 

Add 73

          12        10     7     73 

10 < 73 so need to swap those:

          12        73     7     10 

12 < 73 so need to swap those:

          73        12     7     10 

Add 2 - nothing to do

          73        12     7     10   2 

Add 4 - nothing to do

          73        12     7     10   2  4 

Add 9

          73        12     7     10   2  4   9 

7 < 9 - swap

          73        12     9     10   2  4   7 

Add 1 - nothing to do

          73        12     9     10   2  4   7   1 

We have our heap :D

Now you just remove each element from the top, swapping in the last element to the top of the tree each time, then re-balancing the tree:

Take 73 off - putting 1 in its place

          1        12     9     10   2  4   7 

1 < 12 - so swap them

          12         1    9     10   2  4   7 

1 < 10 - so swap them

          12        10     9      1   2  4   7 

Take 12 off - replace with 7

          7        10     9      1   2  4    

7 < 10 - swap them

          10        7     9      1   2  4    

Take 10 off - replace with 4

          4        7     9     1   2   

4 < 7 - swap

          7        4     9     1   2   

7 < 9 - swap

          9        4     7     1   2  

Take 9 off - replace with 2

          2        4     7     1    

2 < 4 - swap them

          4        2     7     1   

4 < 7 - swap them

          7        2     4     1   

Take 7 off - replace with 1

          1        2     4 

1 < 4 - swap them

          4        2     1 

Take 4 - replace with 1

          1        2 

1 < 2 - swap them

          2        1 

Take 2 - replace with 1

          1 

Take 1

Sorted list voila.

Answer 2

One way to think of heap sort is as a cleverly optimized version of selection sort. In selection sort, the sort works by repeatedly finding the largest element not yet placed correctly, then putting it into the next correct spot in the array. However, selection sort runs in time O(n²) because it has to do n rounds of finding the largest element out of a bunch (and there can be up to n different elements to look at) and putting it into place.

Intuitively, heap sort works by building up a special data structure called a binary heap that speeds up finding the largest element out of the unplaced array elements. Binary heaps support the following operations:

• Insert, which inserts an element into the heap, and
• Delete-Max, which removes and returns the largest element of the heap.

At a very high level, the algorithm works as follows:

• Insert each element of the array to a new binary heap.
• For i = n down to 1:
  • Call Delete-Max on the heap to get the largest element of the heap back.
  • Write this element to position i.

This sorts the array because the elements returned by Delete-Max are in descending order. Once all the elements have been removed, the array is then sorted.

Heap sort is efficient because the Insert and Delete-Max operations on a heap both run in O(log n) time, meaning that n inserts and deletions can be done on the heap in O(n log n) time. A more precise analysis can be used to show that, in fact, it takes Θ(n log n) time regardless of the input array.

Typically, heap sort employs two major optimizations. First, the heap is usually built up in-place inside the array by treating the array itself as a compressed representation of the heap. If you look at a heapsort implementation, you will usually see unusual uses of array indices based on multiplying and dividing by two; these accesses work because they are treating the array as a condensed data structure. As a result, the algorithm requires only O(1) auxiliary storage space.

Second, rather than building up the heap one element at a time, the heap is usually built using a specialized algorithm that runs in time Θ(n) to build the heap in-place. Interestingly, in some cases this ends up making the code easier to read because code can be reused, but the algorithm itself becomes a bit trickier to understand and analyze.

You will sometimes see heapsort done with a ternary heap. This has the advantage of being slightly faster on average, but if you find a heapsort implementation using this without knowing what you're looking at it can be fairly tricky to read. Other algorithms also use the same general structure but a more complex heap structure. Smoothsort uses a much more complicated heap to get O(n) best-case behavior while maintaining O(1) space usage and O(n log n) worst-case behavior. Poplar sort is similar to smoothsort, but with O(log n) space usage and slightly better performance. One can even think of classic sorting algorithms like insertion sort and selection sort as heap sort variants.

Once you have a better grasp of heapsort, you may want to look into the introsort algorithm, which combines quicksort, heapsort, and insertion sort to produce an extremely fast sorting algorithm that combines the strength of quicksort (fast sorting on average), heapsort (excellent worst-case behavior), and insertion sort (fast sorting for small arrays). Introsort is what's used in many implementations of C++'s std::sort function, and is not very hard to implement yourself once you have a working heapsort.

Hope this helps!