1,119 views
1 votes
1 votes
Consider a max-heap of $n$ distinct integers, $n ≥ 4$, stored in an array $\mathcal{A}[1 . . . n]$. The second minimum of $\mathcal{A}$ is the integer that is less than all integers in $\mathcal{A}$ except the minimum of $\mathcal{A}$. Find all possible array indices of $\mathcal{A}$ in which the second minimum can occur. Justify your answer.

2 Answers

2 votes
2 votes

See it by taking 2-3 example cases (For n=4,5 etc) Or Observe that Second minimum can Only be present at One of the Two possible Places :

A. At Any Leaf Node (All the Leaf Nodes are valid places for Second Minimum)

B. If at Intermediate Node then it (Second minimum) will be having Exactly one child which is the Minimum element of the array.

So, By Observation, We can see that 

1. If n= even then Both A and B are valid positions for the Second minimum.

2. If n = Odd then Only A (i.e. Leaf Nodes) is the valid position for Second minimum.

We are done if above things are comfortably observed.

Finally, We can give a Formula for the Possible Array indices of Second minimum which is : $\left \lceil n/2 \right \rceil \,\, to \,\,n$

(Since  Array starts with Index 1)


If Array starts with Index 0, respective changes must  be made i.e. $\left \lceil n/2 \right \rceil -1 \,\, to \,\,n-1$

1 votes
1 votes
For n = 3 arr = { 70, 60, 50 }; //index starts from 1

- we have to compare indices 2 and 3

For n = 4 arr = { 70, 60, 50, 55 }; //index starts from 1

- we have to compare indices 2 to 4

For n = 5 arr = { 70, 60, 50, 55, 40 }; //index starts from 1

- we have to compare indices 3 to 5

For n = 6 arr = { 70, 60, 50, 55, 40, 30 }; //index starts from 1

- we have to compare indices 3 to 6

For n = 7 arr = { 70, 60, 50, 55, 40, 30, 20 }; //index starts from 1

- we have to compare indices 4 to 7

 

So the second minimium can be found clearly within this range of indices CEIL(n/2) to n.

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
3 answers
4