A complete binary min-heap is made by including each integer in [1,1023]…
2016
A complete binary min-heap is made by including each integer in [1,1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________ .
Attempted by 125 students.
Show answer & explanation
Correct answer: 8
Key insight: Every ancestor of the node containing 9 must be less than 9 in a min-heap.
Count the smaller integers: 1 through 8 are smaller than 9, so there are 8 such integers.
To place 9 at depth d, you need d ancestors all smaller than 9, so d cannot exceed 8.
Although the complete heap of 1023 = 2^{10}-1 nodes has depth up to 9, the limited number of smaller values is the restricting factor.
Therefore the maximum depth at which integer 9 can appear is 8.
A video solution is available for this question — log in and enroll to watch it.