Question

Suppose you have a min-heap in an array a[] where: ● The root is stored at index 1 ● There are 15 elements (in a[1]...a[15]) ● There are no duplicates (this is not true in general for heaps; but assume it is true for this problem). Fill in the blanks in the statements below; the resulting statement must be true for any heap obeying the above properties.

There are/is at least ____6_______ elements in the
heap that are/is larger than a[3] "

"There are/is at least ____________ elements in the
heap that are/is smaller than a[5] "

"There are/is at most ______________ elements in
the heap that are/is smaller than a[13] "

"There are/is at most _______________ elements in
the heap that are/is larger than a[15] "

Answer 1

In a Min-Heap both children of a root node contain larger value than their parent / root node. This property must be maintained in the entire heap.

There are/is at least 6 elements in the
heap that are/is larger than a[3] "

The elements are a[6], a[7], a[12], a[13], a[14], and a[15].

"There are/is at least 2 elements in the
heap that are/is smaller than a[5] "

The elements are a[1] and a[2].

"There are/is at most 7 elements in
the heap that are/is smaller than a[13] "

The elements can be a[1], a[3], a[6], a[7], a[12], a[14], and a[15].

"There are/is at most 1 elements in
the heap that are/is larger than a[15] "

The element can be a[14].