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 AncestorHeap(using array)
LEVEL:Beginner
Description
Given an array perform max heapify on it and print the modified array
Input Format
First line contains integer n. Next line contains space seperated integers.
Output Format
Print the array after max heap.
10 1 2 3 4 5 6 7 8 9 10
10 9 6 7 8 2 5 1 4 3
5 10 20 30 80 99
99 80 20 10 30
8 8 15 22 64 21 20 15 30
64 30 20 22 21 15 15 8
Login to see Discussion
Approach
i)in a constructor initialize max size to the size provided by the user
ii)and size to 0
iii) create a heap of int array of size n+1 (here we are taking index from 1 just for simplification)
iv)create a method parent which takes pos as argument and return pos/2
v)create a method left_child which takes pos as argument and return 2* pos
vi)create a method right_child which takes pos as argument and return 2*pos + 1
vii)create a method is_leaf where is pos is greater than or equal to size/2 and less than or equal to size return true
else return false
viii)create a method swap which swaps the content of two positions of heap array which are given as argument
ix)create a method max_heapify which takes pos as argument
x)if is_leaf of pos is true just return
xi)if Heap[pos] < Heap[leftChild(pos)] or Heap[pos] < Heap[rightChild(pos)] go to next steps
xii) if Heap[leftChild(pos)] > Heap[rightChild(pos)] perform swap(pos,left_child(pos)) and max_heapify(left_child(pos))
xiii)else swap (pos,right_child(pos)) and perform max_heapify(right_child(pos))
xix) create a method insert which takes val as arguement
xx)assign val to heap[++size] and assign size to curr
xxi)while Heap[current] > Heap[parent(current)] perform swap(current, parent(current)) and current = parent(current)
xxii)create a method print which print the max_heapified array
xxiii)in main method take the required inputs from the user such as initial array size and array elements
xxiv)traverse the array and send the array elements to the maxhepify function to perform required operations and finally print
the array
Time Complexity: O(n)
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