Array ( [0] => [1] => questions [2] => Popular-Algorithms [3] => Heap-Sort )
For the given array apply heapify and perform heapsort on it
First line contains n representing no of elements in the array Second line contains n space separated integers which are array elements
Print the sorted array
5 1 5 7 4 2
1 2 4 5 7
8 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
10 45 21 4 8 5 6 7 8 25 24
4 5 6 7 8 8 21 24 25 45
Login to see Discussion
i)create a method heap_sort which takes array as input
ii)assign length of array to n;
iii)run loop from n/2 to 0 and perform heapify on arr,n,i
iv)run loop from n-1 to 0 , swap arr[0] and arr[i] and perform heapify on arr,i,0
v)create a method heapify which takes arr,n and i as argument
vi)assign i to largest, 2*i+ 1 to l and 2*i+2 to r
vii)if l < n and arr[l] > arr[largest] assign l to largest
viii) if r
ix)if largest is not equal to i swap arr[i] and arr[largest] and perform heapify on arr,n,largest;
x)create a method printArray which print the array from i=o to i
xi)in main method take n as input for no of elements in array
xii)read the array integers
xiii)call the sort function and finally print the array
Time Complexity: O(n logn)
Space Complexity: O(n)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution