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

2 Answers

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.

• Thnks for answer, but tell me how siblings are taken into account ? – user3699192 Feb 1 '17 at 19:18
• That would be part of the exercise. – Yuval Filmus Feb 1 '17 at 21:29
• @user3699192, I suggest you familiarize yourself with our policy on comments: cs.stackexchange.com/help/privileges/comment. Also, may I offer some suggestions about how to make the most of this site? People are willing to help you, but there is an expectation that you will do your part. The site works best when you are willing to put in a lot of work on your own and show (e.g., in the question) what approaches you've tried/considered and why you rejected them or where you got stuck. Don't expect someone else to do all your work for you or to avoid the need to do thinking of your own. – D.W. Feb 1 '17 at 22:59