Locating nodes Let A1 25 store the keys of a minheap with 20

Locating nodes. Let A[1 25] store the keys of a min-heap with 20 items. Assume that all the keys are distinct. Answer the following questions: What are the possible indices i so that A[i] contains the second smallest key? Why? What are the possible indices i so that A[i] contains the third smallest key? Why? What are the possible indices i so that A[i] contains the largest key? Why? Let\'s flip this question around. Suppose A|[1 25) is storing the keys of a max-heap. Answer questions a. b. and c again.

Solution

4) a. The second smallest key should be either in A[1] or A[2].
b. The third smallest key can be in any place from 1 - 6.
c. The largest key can be 15-19 or 10-14.

Let us assume this is max heap.

a. The second smallest key can be 7-9 or 4-6.
b. The third smallest key can be 1,2,3,4.
c. The largest key is in 0.