Heap Sort
- Heap sort algorithm is a comparison algorithm.
- Heap sort begins with construction of Heap tree with specified elements and then removing the largest item and placing it at the end of the sorted array.
- After removing the largest item we need to reconstruct the heap tree by following rules of tree.
- This process continuous until all elements gets arranged.
- Heap sort uses two heap operations insertion and root deletion.
Building the heap tree:
- We need to construct the heap tree with given elements.
- Heap tree rule is “Parent node should contain greater value than both of its Children”.
The tree representation is used to understand the algorithm more easily while sorting the element of this array.
Note: Start comparing nodes from size/2 node(here total 6 nodes – hence starts with 3rd node).
3rd node comparison:
After swapping:
2nd node checking:
Swapping not required:
Checking first node:
- Element 19 will move to its position(parent location).
- Element 15 need to compare with next level elements also.
After comparison, we need to swap 17 and 15; finally we constructed Heap tree
Performing “deleteMax” operations:
- Heap tree root element is the highest element in the array.
- We need to swap the root element with last location element as highest element sorted.
After sorting, we need to re-construct the Heap tree to get the next highest element as root element.
- 10 replace with 17
- 15 comes to element 17 position
- 10 will store into element 15 location
Final tree is:
