Array ( [0] => [1] => questions [2] => Strings [3] => Heap(using-array) )
Given an array perform max heapify on it and print the modified array
First line contains integer n. Next line contains space seperated integers.
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
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