index of 3rd smallest element in max heap

Question

How do i find the possible indices of 3rd smallest element in max heap of 1 to n distinct elements? I know that the smallest element will anywhere in the leaf. the second smallest will be anywhere from n/2 to n for n greater than 3 But i dont not know to to calculate for 3rd smallest. Any suggestions?

Answer 1

The third-smallest element has at most two descendants, which means that its child(ren) are leaves, or it is a leaf. (To prove this, you also have to prove that it is impossible for an element with only one child to have a non-leaf as the child. Easy but tedious.)

Leaves, as you almost note, have indices in the range [floor(n/2)+1, n]. If n/2 is an integer, then that element has exactly one child (which is a leaf), so adding that gives the range of indices which might contain the second-largest element.

An element whose first child is in the leaf range [floor(n/2)+1,n] has at most two children, and no non-leaf child. That range is contiguous with the [ceil(n/2),n] range, and the union of the two ranges provides all the possible positions for the third-largest element.

The first child of the element at i has index 2i, so the first element whose first child is at least floor(n/2)+1 is floor(n/4)+1.

Thus, the possible indices at which you could find the third-largest element is the range: [floor(n/4)+1,n].

---

Here's another approach. Take some element at index i. Its immediate children are 2i and 2i+1; its grandchildren are 4i, 4i+1, 4i+2, 4i+3 and, in general, it's descendants at level k are 2ki, 2ki+1, ..., 2ki + 2ki-1; in summary, [2ki, ..., 2k(i+1)-1 ]. These ranges are, of course, non-overlapping (indeed, unless i is 1, they're not even contiguous). So if i has at least one descendant at level k, it also has a complete set of descendants for all k' < k, of which there are 2k-2.

From all of that, we can conclude:

• If n ≥ 2ki and n < 2k(i+1), then i has:

  • 2ki-2 descendants at some level less than k

  • n - 2ki+1 descendants at level k;

  • Total: n-1 descendants.

• If n ≥ 2k(i+1) and n < 2k+1i, then i has:

  • exactly 2k+1-1 descendants.

Roughly speaking, this means that the last 2k elements are not found in the first 1/2k part of the heap's underlying array.