4 Heap sort

One main use of the heap data structures is for heap sort. The heap sort algorithm inserts all items (from an unsorted array) into a heap, then remove values from the root of a heap until the heap is item. As removed from the heap, the values become sorted.

Because the time complexities of both the insertion algorithm and deletion algorithms belong to Θ(log(n)) (where n is the number of items in the heap), the time complexity of the heap sort algorithm belongs to Θ(n log(n)).

Note that heap sort can be done in place with the array to be sorted. This can be done by removing values from the array in increasing index order while the values are inserted into the heap. This is possible because the heap only needs to use as many elements in the array as elements removed. The boundary between the heap and the unsorted array moves from the beginning to the end.

When we remove items from the heap, we fill the array from the end back to the beginning. This is possible because as the size of a heap shrinks, the serial number of its last leaf decrements. In other words, the boundary between the sorted array and the heap moves from the end to the beginning.