Binary Heaps

A binary heap is always a complete binary tree: every level is full except possibly the last, which fills from the left. So its shape, and hence its height, depends only on the number of keys.

Levels 0 to 4 hold \(1 + 2 + 4 + 8 + 16 = 31\) keys, so the 32nd key starts level 5. The deepest leaf is therefore 5 edges below the root, matching \(\lfloor \log_2 n \rfloor = \lfloor \log_2 32 \rfloor = 5\).

Answer: 5

No option starts with the smallest key, 11, so the heap meant is a max-heap. Build it bottom-up, sifting down from the last internal node (position 5) back to the root:

• 111 is already larger than its child 93; 11 swaps with its larger child 131; 90 stays above 75 and 33.
• 101 swaps with its larger child, now 131.
• At the root, 82 swaps with 131, then with 111, then with 93.

The heap is [131, 111, 90, 101, 93, 75, 33, 11, 44, 82], and inserting the keys one at a time gives the same first three. Option C is impossible because 11, the smallest key, cannot have children in a max-heap; A and B do not start with the maximum, 131.

Answer: D

In a min-heap every parent is smaller than its children, so the maximum element cannot have a child: it must be a leaf. With the 105 elements at indices 1 to 105, the nodes with children are indices 1 to \(\lfloor 105/2 \rfloor = 52\), and the leaves are indices 53 to 105, which is \(105 - 52 = 53\) positions.

Every leaf is possible: put the maximum at any chosen leaf and fill the other positions with the remaining elements in increasing order of index; each parent is still smaller than its children. So \(k\) has 53 possible values (indices 52 to 104 with 0-based indexing, still 53).

Answer: A