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 _________.

A complete binary tree with $N = 1023 = 2^{10} - 1$ nodes has height $h = \log_2(1023 + 1) - 1 = 9$, meaning nodes are located at depths from $0$ to $9$.

In a min-heap, every ancestor of a node containing value $x$ must have a value strictly less than $x$.

For the integer $9$:

• The elements strictly smaller than $9$ are $\{1, 2, 3, 4, 5, 6, 7, 8\}$, which gives at most $8$ distinct values.

• Therefore, on any path from the root down to the node containing $9$, there can be at most $8$ ancestors.

Since each step in depth corresponds to one ancestor on the path to the root:

Because the heap has depth up to 9, depth 8 is present, and we can place values $1, 2, 3, 4, 5, 6, 7, 8$ along the path at depths $0, 1, 2, 3, 4, 5, 6, 7$ and place $9$ at depth $8$.