Array ( [0] => [1] => questions [2] => HackwithInfy-Previous-Questions [3] => Heapify )
For the given input array perform heapify and print the array
First line contains n which is no of elements in the array Second line contains n space separated integers which are array elements
print the heapified version of the array
10 100 25 1 4 213 12 18 57 32 56
1 4 12 25 56 100 18 57 32 213
8 8 7 2 5 4 9 32 25
2 4 8 5 7 9 32 25
5 5 4 3 2 1
1 2 3 4 5
Login to see Discussion
i)create a method min_heap which takes arr,m and n as argument and return the array
ii) assign a[m] to t and 2*m to j
iii)if j is less than n and a[j+1] is less than a[j] increment j by one value
iv) if t is less than a[j] break the loop
v)else if t is greater than or equal to a[j] assign a[j] to a[j/2] and 2*j to j
vi)repeat steps iii,iv and v till j is less than or equal to n
vii)assign t to a[j/2]
viii)return the array
ix)create a method build_heap which takes array and n as argument
x)run loop from n/2 to 1 and perform min_heap on a,k,n
xi)in main method take the input of n and array
xii)call the build_heap method
xiii)finally print the heapified version of the array
Time Complexity: O(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