The Maxheap sorts the elements in increasing order whereas Minheap sorts the element in decreasing order.To sort the heap three steps have to be followed
- Heapify -The process picks the largest child key and compare it to the parent key. If parent key is larger than key then heapify quits, otherwise it swaps the parent key with the largest child key. So that the parent now becomes larger than its children.
- Build Heap - Use the procedure 'Heapify' in a bottom-up fashion to convert an array into a heap. The process starts from last nodes and not the leaves.
- Heap Sort - Sorting is done by removing the max element and storing in array .The storage starts from last position and goes till first index of array.
- Build Heap Algorithm will run in O(n) time
- There are n-1 calls to Heapify each call requires O(log n)time
- Heap sort program combine Build Heap program and Heapify, therefore it has the running time of O(n log n) time
- Total time complexity: O(n log n)
Given an array in Fig 1 .We need to convert it to Maxheap and sort it.
Array is converted to heap in Fig 2
The further steps are illustrated through following figures: