Beginner
1. Binary Search2. Linear Search3. Fibonacci Search4. Bubble Sort5. Insertion Sort6. Selection Sort7. Quick Sort8. Merge Sort9. Addition of two matrixes10. Subtraction of two matrixes11. Multiplication of two matrixes12. Transpose of given Matrix13. EUCLIDIAN GCD ALGORITHM14. Fabinocci Numbers with matrix multiplication15. Fast Exponential16. Modular inversion17. Prime seiving18. Heap(using array)19. Heapify20. Heap Sort21. Linear Probing22. Open Addressing23. Collision Avoidance24. Binary Search Tree Traversal Techniques25. Finding Kth Largest Element in Binary Tree26. Diameter of a Binary search tree27. Depth of Binary Tree28. Number of Nodes in BST29. Convert Array to Binary Tree30. Convert Array to General Tree31. Lowest Common AncestorHeapify
LEVEL:Beginner
Description
For the given input array perform heapify and print the array
Input Format
First line contains n which is no of elements in the array Second line contains n space separated integers which are array elements
Output Format
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
Approach
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