Eleven Swaps Not Thirty Four

Take a perfect binary min-heap holding exactly 15 elements, so there are 8 leaves, 4 nodes one level up, 2 above those, and the root.

Building it bottom up runs sift-down at every internal node. A node at height hh can sink at most hh levels, and a perfect heap of nn nodes has n+12h+1\frac{n+1}{2^{h+1}} nodes at height hh:

swaps≤∑h=1315+12h+1⋅h\text{swaps} \le \sum_{h=1}^{3} \frac{15+1}{2^{h+1}} \cdot h

Evaluate that worst case.

A

49

B

11

C

14

D

34