All About Heap Sort -- Part 1

HeapSort is a sorting algorithm . It performs in place sorting . Its complexity it O(n lg n).
It makes use of a data structure called heap. The heap data structure is like an array which looks like a complete binary tree.If you imagine the heap array as a tree then each node in the tree will have left and right children . Each of the nodes in the tree map on to elements in the array . Every parent at index (i) will have a left child at index (2 * i ) and a right child at index (2 *i +1 ) in the array . Nodes in the heap follow the heap property . Heaps can be a max heap or a min heap.
In a max heap every Parent will have a higher value than any of its children . Its the opposite in the case of min heap. For the heap sort algorithm a max heap is used , generally a min heap is used for a priority queue.

Since a heap of (n) elements is like a complete binary tree its height is (lg n ) and all basic operations run in a time proportional to the height of the tree . Heap is a complete binary tree filled with elements at all levels except the last one . So the max number of elements in a heap of height (h) is (pow(2,h+1) - 1) . The minimum number of elements is equal to the number of elements in a heap of height (h-1) + 1 element. We add the extra one element because in the actual heap there would be at least one element on the last row containing leaves.
So the minimum number of elements = (pow(2,h) -1 ) + 1

The height of a heap is actually = floor(lg n ) . Since , a heap with height h will have elements (n) = pow(2,h) <= n <= pow(2,h+1)-1 < pow(2,h-1) and hence
h <= lg n < 1 =""> height = floor ( lg n )