# 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?

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$$)

• What do you think? Have you tried to solve this for small $n$? – Yuval Filmus Feb 1 '17 at 15:54

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