Heap operations: algorithms, Heap Sort

Explain, with example the basic heap operations and write the algorithms for the same. Heap Sort

Heap sort operates by first converting the list in to a heap tree. Heap tree is a binary tree in which each node has a value greater than both its children (if any). It uses a process called "adjust to accomplish its task (building a heap tree) whenever a value is larger than its parent.

The time complexity of heap sort is O(nlogn). Algorithm:

1. Construct a binary tree

• The root node corresponds to Data[0].

•  If we consider the index associated with a particular node to be i, then the left child of this node corresponds to the element with index 2*i+1 and the right child corresponds to the element with index 2*i+2. If any or both of these elements do not exist in the array, then the corresponding child node does not exist either.

2. Construct the heap tree from initial binary tree using "adjust" process.

3. Sort by swapping the root value with the lowest, right most value and deleting the lowest, right most value and inserting the deleted value in the array in it proper position.

Example: Sort the following list using heap sort algorithm.

5        8        2        4        1        3        9        7        6        0