Finding element in binary min-heap

Question

I am trying to answer two questions. Can some one check my answer and let me know if its correct or not?

Question 1: Which locations in a binary min-heap of n elements could possibly contain the third-smallest element?

Answer 1: So I know this is a tree where lowest number is at top, so 3rd smallest element is in the 3rd row.

Question 2: Which locations in a binary min-heap of n elements could possibly contain the largest element?

Answer 2: The smallest number is at top of tree, so the largest has to in the last row.

Answer 1

For 1, the second row could contain the second and third smallest. For 2, is your heap the same height everywhere? In the first example, could 2 have children and 3 not?

Answer 2

Your answer to the first question is not correct. Consider the tree on three nodes with root $R$, and children $V_1$ and $V_2$. This tree only has two levels, but one of $V_1$ or $V_2$ is still the 3rd smallest element.

As for the second question, a heap need not be completely balanced, and the maximal element of the heap need not be in the last row.

Answer 3

Okay, so the problem is to find the $k^{th}$ smallest entry in a min-heap. Here is a simple algorithm to find it in a min-heap $H$ containing $n$ entries.

You'll agree with me that the root is the minimal element of your heap. So, let's delete it. To keep your heap properties, you've certainly seen a nice algorithm to do it, certainly named either down-heap, bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down or extract-min. So let's apply this algo. You've now a new min-heap $H_1$ with $n-1$ entries and whose root is the $1^{st}$ smallest entry.

Now you can simply apply again this procedure $k-1$ times on your min-heap to get the $k^{th}$ smallest element ! But this won't be true if your minimal element is present more than once in your heap. So your algorithm should keep track of the root value and count only the roots that are different from the previous one.

To get the answer to your first question, you may simply consider the min-heap of pair consisting of the elements of your heap and their index in that heap, using your newly designed algorithm.

But I can't give you a "general" answer to your question since it's relying on the way you're adding elements to your heap : it may be in the second row as well as in the third row, but if we consider the heap containing $\{1,1,1,1,1,1,1,1,1,1,2,3\}$, I think you see my point : the 3 smallest entry is $3$ but is not even in the $3^{rd}$ row... So you should think about those degenerated cases as well.

To get the answer to your second question you may use the same method as before, but for $n-3$... But you should again be cautious about multiple entries of the same value, which are messing things up.

PS : hence my answer to both of your question is kind of "everywhere", excepted for the root ; unless your definition of min-heap specifies that it doesn't contain multiple entries of the same value.