I have already demonstrated one of the binary heap usage scenarios – priority queue. Today I want to show another binary heap usage example – heap sort. The algorithm consist of two steps:

• on the given set of numbers ensure max-heap invariant (the value of each node is not bigger than value of its parent with biggest element at the root)
• while heap is not empty remove first (max) item from the max-heap

The first part is almost identical to the way we ensured binary heap invariant during delete operation. In order to make second step space efficient, we need do following things:

• swap first (max) item with the last one in the max-heap
• decrease size of the max-heap by 1
• ensure max-heap invariant starting from the first item

Let’s sort items [3 4 1 3 5 1 2]. As always I’ll use colors to specify parent, child or items to be swapped:

Step #1

The binary tree constructed from the given items does not conform max-heap invariant:

     3
   4   1
  3 5 1 2

To ensure max-heap invariant for the given set we need to take each node in the tree (except leafs) and recursively ensure it is bigger than any of the child nodes. As a reminder, our binary heap stores items starting from index 1, so we need to temporarily add null item at the beginning: [null 3 4 1 3 5 1 2]

At this point we have binary max-heap:

     5
   4   2
  3 3 1 1

Step #2

Swap first (max) item with the last one and ensure max-heap invariant:

Finally we remove leading null item and we have sorted items! Implementation (tests) of the heap sort is heavily based on the binary heap implementation:

Complexity: O(n·logn)