HeapSort: Algorithm and Example

Presented here is one variation of Williams's HeapSort algorithm.1 It operates by transferring the elements in the array-to-be-sorted into a heap (this is Phase 1) and then (in Phase 2) transferring those elements back into the array. The version shown here uses a max-heap, but one could just as well use a min-heap. (With a max-heap, the elements come out of the heap in order from greatest to least; with a min-heap it would be from least to greatest).

Expressed in Java, here is HeapSort. To keep things simple, we assume that the array to be sorted is of type int[]. 

public static void heapSortInt(int[] a) {
   // Phase 1: heap construction
   MaxHeapOfInt heap = new MaxHeapOfInt();
   for (int i=0; i != a.length; i++) {
      heap.insert(a[i]);
   }

   // Phase 2: heap extraction
   for (int i = a.length-1; i >= 0; i--) {
      a[i] = heap.deleteMax();
   }
}

Example

We consider the seven-element array 

   0    1    2    3    4    5    6 
+----+----+----+----+----+----+----+
|  8 | 15 |  4 | 11 | 22 | 18 |  9 |
+----+----+----+----+----+----+----+

During each iteration of the loop in Phase 1 of the HeapSort algorithm, one element of the array is inserted into an initially empty max-heap. Here is what the heap will look like at the end of each of the seven iterations (with underlines indicating the tree node inserted and any other node whose content changed due to the new element having been sifted up within the tree).

After 1st iteration After 2nd iteration After 3rd iteration After 4th iteration After 5th iteration After 6th iteration After 7th iteration
8 inserted: 
     8
 15 inserted:
       15
      /
     /
    8
 4 inserted:
      15
     /  \
    /    \
   8      4
 11 inserted: 
        15
       /  \
      /    \
     11     4
    /
   /
  8
 22 inserted: 
       22
      /  \
     /    \
   15      4
  /  \
 /    \
8      11
 18 inserted: 
         22
        /  \
       /    \
      /      \
     /        \
   15         18
   / \       /
  /   \     /
 8     11  4
 9 inserted: 
         22
        /  \
       /    \
      /      \
     /        \
   15         18
   / \       /  \
  /   \     /    \
 8     11  4      9

During each iteration of the loop in Phase 2 of the algorithm, the largest value in the heap is removed and placed into its proper location into the array. Underlines show each node whose value changed as a result of the last node's value having been placed there and then sifted down.

After 1st iteration After 2nd iteration After 3rd iteration After 4th iteration After 5th iteration After 6th iteration
22 removed: 
         18
        /  \
       /    \
      /      \
     /        \
   15          9
   / \        /
  /   \      /
 8     11   4
 18 removed: 
         15
        /  \
       /    \
      /      \
     /        \
   11          9
  /  \
 /    \
8      4
 15 removed: 
         11
        /  \
       /    \
      /      \
     /        \
    8          9
   /
  /
 4
 11 removed: 
      9
     / \
    /   \
   /     \
  /       \
 8         4
 9 removed: 
      8
     /
    /
   /
  /
 4
 8 removed: 
      4

Footnotes

[1] Williams's version of HeapSort ("Algorithm 232 — Heapsort", Communications of the ACM 7:6 (1964) pp. 347-348) is an "in-place" algorithm, meaning that the space occupied by the array-to-be-sorted and the heap coincide. In the version of the algorithm presented here, the heap is a separate structure from the array and thus O(n) space is required (aside from the array).