Heap Sort

It is similar to insertion and deletion. Insert the whole in a (Min or Max) heap. Delete the whole array by moving elements at last one by one.

Example: Sort the given array

                arr[] = {9,4,8,2,5,6,7}

    Apply Deletion:

    Apply Deletion:

    Apply Deletion:

    Apply Deletion

    

    Apply Deletion

    Apply Deletion

    Apply Deletion

Sorted Array using Heap Sort

After deletion Max Heap convert to Ascending order array

After deletion Min Heap convert to Descending order array

Time complexity of Inserting and Deleting an Element: O(log(n)+log(n))

Time complexity for performing above operation on n Element: O(n*2*log(n))

Therefore time complexity for Heap sort will be: O(nlog(n))