Heapsort

The heapsort is a type of sort that uses a maxheap. It has two main steps: 1. Convert an input array into a maxheap, 2. Remove the biggest value from the heap and put it at the end.

Let’s go over the Step 1 first

Step 1

Algorithm:

  1. Set curNode to the (n / 2) - 1 (this way we skip all the leaf nodes that by default are valid maxheaps)
  2. Repeatedly decrease curNode until curNode is equal to the root node
    1. Think of the subtree pointed to by curNode as a maxheap
    2. Keep shifting the top value until that subtree becomes a valid maxheap

By the end of Step 1, the inputted array will be sorted as a maxheap

Step 2

Algorithm:

  1. Extract the biggest value from the maxheap (root node).
  2. Copy the value from the bottom-most right-most node and put it in the root
  3. Delete that node
  4. Repeatedly swap the just-moved value with the larger of its two children until the value is greater than or equal to both of its children
  5. Put the extracted value into the freed-up slot

Example:

arr[8] = { 0, 3, 9, 1, 5, 4, 18, 21};

Even though we will be using an array as the data structure, you should draw a tree to visualize the data easier.

           0
      3         9
  1     5    4   18
21

curNode = (8 / 2) - 1 = 3. Slot 3 has the value 1

           0
      3         9
  1     5    4   18
21

Think of curNode and its children as a subtree. Is it a valid maxheap?

  1
21

No, we need to swap them

Now it is valid.

**Decrease curNod**e. Now it points to the value at slot 2, 9. Is that subtree a valid maxheap?

  9
4   18

No, swap 9 and 18

  18
4   9

Now it is valid. Decrease curNode. Now it points to the value at slot 1, 3. Is that subtree a valid maxheap?

      3
  21     5
1

No, swap 3 and 21

     21
  3      5
1

Now it is valid. Decrease curNode. Now it points to the value at slot 0, 0. Is that subtree (now entire tree) a valid maxheap?

           0
     21        18
  3     5    4    9
1

No, swap 0 and 21

          21
      0       18
  3     5   4    9
1

Now we need to swap 5 and 0 as well

          21
     5        18
  3     0   4    9
1

Now it is valid.

Here is what the array look like now:

arr[8] = { 21, 5, 18, 3, 0, 4, 9, 1 }

Extract the biggest value from the maxheap and copy the value from the bottom-most right-most node into the node

        1
   5        18
3     0   4    9

{ 1, 5, 18, 3, 0, 4, 9,  }

Make all the necessary swaps to make it a maxheap

       18
   5        1
3     0   4    9

       18
   5        9
3     0   4    1

{ 18, 5, 9, 3, 0, 4, 1,  }

Now it is valid. We insert the 21 back into the array at the freed-up slot. We ignore this newly inserted item when drawing out our tree, however.

{ 18, 5, 9, 3, 0, 4, 1, 21 }

       18
   5        9
3     0   4    1

Extract 18 and replace it with the bottom-most right-most node and do all necessary swaps

       1
   5        9
3     0   4

       9
   5        1
3    0    4

       9
   5        4
3    0    1

Insert 18 into the freed-up slot

{ 9, 5, 4, 3, 0, 1, 18, 21 }

Extract 9, etc.

       1
   5        4
3    0

       5
   1        4
3    0

       5
   3        4
1    0

{ 5, 3, 4, 1, 0, 9, 18, 21 }

Extract 5, etc.

       0
   3        4
1

       4
   3        0
1

{ 4, 3, 0, 1, 5, 9, 18, 21 }

Extract 4, etc.

    1
3        0

    3
1        0

{ 3, 1, 0, 4, 5, 9, 18, 21 }

Extract 3, etc.

    3
1        0

    0
1

    1
0

{ 1, 0, 3, 4, 5, 9, 18, 21 }

Extract 1, etc.

0

{ 0, 1, 3, 4, 5, 9, 18, 21 }

Extract 0

{ 0, 1, 3, 4, 5, 9, 18, 21 }

The big-o of the heapsort is O(n * log(n)) for n items - The big-o of Step 1 is O(n) - The big-o of Step 2 is O(n * log(n)) (every time you remove an item it takes log(n) steps to reposition the array, and you remove n items) - The total is O(n + n * log(n)), which simplifies to O(n * log(n))