Heap Sort - Coursera Algorithms

Heap Sort is an in place sort that builds a max binary heap and then repeatedly deletes the maximum element. It's not stable and it's inner loop takes longer than Quick Sort. It has poor cache usage. To build a heap, it takes O(N) and for sort, it takes O(NlogN).

Following is the program:

Related Posts:

Binary Heap

Binary Heap - Coursera Algorithms

A binary tree is either empty or points to a root node with links to left and right binary trees. A tree is complete if it is balanced perfectly, excluding the bottom level. A binary heap is an array representation of a heap ordered complete binary tree.

Max node is root at a[1]. For a node k, it's parent is at k/2 and it's children are at 2k and 2k+1.
Swim: When a child node is greater than parent, keep exchanging them till they are ordered.
Sink: When a parent node is lesser than child, keep exchanging them till they are ordered.
In insert operation, add the child at end and swim it. --> O(logN)
In delete operation, exchange root with node at end and sink the top node. -->O(logN)

Following is the program: