If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

Question

If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are from $\color{Blue}1$ to $\color{Blue}n$)

Answer 1

Let $D(i)$ denote the number of descendants of the $i$th node. In a min-heap, all $D(i)$ nodes below node $i$ must have a larger value than node $i$. Hence, the $n-D(i)$ largest values $n-D(i)+1,\ldots,n$ cannot be put in node $i$. It turns out that $n-D(i)$ can be put in node $i$, and so the maximum possible value for node $i$ is $n-D(i)$. To see how this can be achieved, fill in the descendants of node $i$ by $n-D(i)+1,\ldots,n$, and fill in the remaining nodes in any way so that the min-heap property is satisfied. The integers available for the parents of node $i$ are all less than $n-D(i)$ and so the min-heap property can be satisfied. The sibling of node $i$, the siblings of the ancestors of node $i$, and the descendants of these siblings, all necessarily contain values smaller than node $i$ because the values larger than $n-D(i)$ have been used up, and this is fine because we want node $i$ to have the largest possible value. There is no violation of the min-heap property, which only concerns relations between a node and its parent (and therefore all its ancestors) or its children.

To obtain the smallest possible value for node $i$, let $A(i)$ denote the number of ancestors of node $i$. This value is the number of nodes in the unique path from the root to node $i$ (including the root node but not including node $i$). These $A(i)$ nodes must have values less than node $i$, and so the smallest possible value for node is at least $A(i)+1$. Is this bound achievable? Yes, put values $1,2,\ldots,A(i)+1$ as the values on the path from the root node to node $i$ (where node $i$ takes value $A(i)+1$). Observe that the remaining nodes can be filled in with the remaining values in such a way that the min-heap property is satisfied. The sibling of node $i$, the siblings of the ancestors of node $i$, and the descendants of all these siblings, as well as the descendants of node $i$, will all have a larger value than $A(i)+1$, and this doesn't violate the min-heap property.

Answer 2

For a vertex $x$, let $a$ denote the number of vertices above $x$ (i.e., its parent, its grandparent, and so on), and let $b$ denote the number of descendants of $x$ (excluding $x$). Identifying $x$ with the number put in $x$, we see that $x > a$ and $x + b \leq n$. This shows that $a+1 \leq x \leq n-b$. It is very likely that both extremes are achievable, and it could be a nice exercise to confirm or refute this conjecture.