Heapsort

Heapsort is a type sorting that uses binary heaps for sorting

• It is siilar to selection sort in the way that it finds the best element and moves it to the front/back of the collection.
• The difference is that instead of scanning throught he entire collection to find the smallest/largest item, it uses a heap to find the best element in O(lgn) time. The heap data structure was created to implement heapsort.

The Original Sort

Created by J. W. J. Williams.

1. Create a priority queue O(1)
2. Add all elements to it O(N lg N)
3. Remove the best element one at a time and add it to the data structure. O(N)

Space and Time Complexity Time is O(N lg N) Space is O(N) Auxilliary is O(N)

Improved Sort:

Robert W Floyd invented this method. Inserting each element into an empty heap is a O(N lg N) process. You can actually build the heap in linear time, although the asymptotic efficiency remains O(N lg N).

Floyd's heapify algorithm builds the heap from bottom up.

• Compare each node to its children and move nodes down (sink) so that parent nodes are always larger than their children.
• Leaf nodes can be ignored.

In a complete binary tree there are ceil(n/2) leaves and floor(n/2) non-leaf nodes.

In-Place Sorting

Heapify is a linear time operation.

• each node at height h at most h swaps
• in a complete binary tree with n node, there are ceil(n/2^(h+1)) nodes at height h.