recategorized by
2,649 views
8 votes
8 votes

Construct the Max Heap assuming the following set of integers were inserted into it in given order
                            

                                             20, 32, 1, 3, 4, 5, 6, 7, 10, 23, 45

Postorder traversal of the resultant max heap was stored in a array A with an index variable  inorder (Starting from 0). Similarly level order traversal was stored in the array B using index variable j in order (Starting from 0). For particular element, respective i and j location values from A and B were obtained and |i – j| is calculated. What could be the maximum possible value for |i – j|?

recategorized by

2 Answers

4 votes
4 votes

according to ques array A for postorder traversal of the resultant max heap.

and  level order traversal was stored in the array B

A

7 3 10 20 4 23 32 5 1 6 45

B

45 32 6 10 23 5 1 7 3 20 4

from arrays A and B as shown above we can clearly find max value of |i-j| .

in array A 45 is in index 10 whereas in array B 45 is in index 0 so max value of |i-j| is 10-0=10

0 votes
0 votes

postorder : 3,7,10,4,20,23,32,1,5,6,45

Levelorder :45,32,6,10,23,1,5,3,7,4,20

i-j = 10-0= 10

 

Answer:

Related questions

0 votes
0 votes
1 answer
1
kallu singh asked Jan 17, 2019
435 views
0 votes
0 votes
1 answer
2
Aboveallplayer asked Dec 1, 2016
663 views
You are given a heap containing N elements. Write a procedure which takes as input a parameter k, and outputs the k'th smallest number in the heap. The running time of th...
5 votes
5 votes
1 answer
3