At which levels in a max-heap might the `k`-th largest element reside?

Question

Consider a max-heap containing n elements. I'm interested in determining the levels within the heap where the k-th largest element could be located, where 2 <= k <= floor(n/2). It's assumed that all elements are distinct (This is the exercise 6.1-5 from CLRS ed.4).

Given that nodes from index floor(n/2)+1 to n are leaves and the node at index 1 is the root, our focus is on other nodes. It's established that the k-th largest element cannot be at level k+1. This is because nodes at level k+1 have k ancestors, implying that there are at least k larger elements than them. Consequently, they cannot be the k-th largest element. However, determining the general levels where the k-th largest element might be found remains a challenge.

I came across a suggestion on this platform advising to search for the k-th largest element in a max-heap within indices from k to 2k. While I comprehend the reasoning behind the lower bound, as in the best-case scenario where the array is sorted, the k-th largest element is at index k, I'm unsure why the search should be limited to index 2k. This raises a new question: What is the height of the element at index k in a max-heap?

I would greatly appreciate any assistance on this matter!

Answer 1

Here is a computational solution to a more specific problem: finding the admissible indices i for the kth largest element in a max-heap of n distinct elements. The level L can be computed from the index via L=⌊lg i⌋ + 1. The key is the ANCESTORS(i, n) and DESCENDANTS(i, n) functions, giving the number of ancestors and descendants of node i in a max-heap of n distinct elements, respectively. Clearly

ANCESTORS(i, n) = ⌊lg i⌋,

and the recursion

DESCENDANTS(i, n) = BOOL(2 * i ≤ n) + BOOL(2 * (i + 1) ≤ n) + DESCENDANTS(2 * i, n) + DESCENDANTS(2 * i + 1, n),

after some work gives

DESCENDANTS(i, n) = 2 (-1+2^Floor[Log[(1+n)/(1+i)]/Log[2]]-2^Floor[Log[(1+n)/i]/Log[2]] i+2^Floor[Log[(1+n)/(1+i)]/Log[2]] i)+(1+n) Floor[Log[(1+n)/i]/Log[2]]-(1+n) Floor[Log[(1+n)/(1+i)]/Log[2]], which for a fixed n is monotonically non-increasing in i.

Given these functions, two necessary conditions are ANCESTORS(i, n) ≤ k - 1 and DESCENDANTS(i, n) ≤ n - k. Adding one to the first inequality gives L ≤ k as you have pointed out. Unfortunately, I couldn't get a closed-form solution for the DESCENDANTS inequality. Moreover, I am not sure whether partially filling the max heap with the kth largest value, and all nodes (transitively) related to it, can always be extended into a valid max-heap. If some partially filled max-heaps cannot be extended properly, then the constraints on i are stronger than the two inequalities given here.

Answer 2

Bad news.

• If k = 1, then the first element is of course the root of the heap;
• If k > 1, then the kth element (1-indexed) can be almost anywhere.

As an example, let n=31, k = 10, and the elements 1, ..., n, with the kth largest element being 22. Consider the two following maxheaps, which have the same elements:

Heap a
31
[22] 30
21 20 29 28
19 18 17 16 27 26 25 24
 8  7  6  5  4  3  2  1 23 15 14 13 12 11 10  9

Heap b
31
30 27
29 26 25 24
28 23 21 20 19 18 17 16
[22] 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

In heap a, the kth element is at depth 2. In heap b, the kth element is at the maximum depth in the heap.

The only restrictions are that you can put at most k-1 ancestors above the kth element, and at most n-k descendants below the kth element; the only constraints on the depth d of the kth element in a heap of height h are k <= d and 2^(h-d)-1 <= n-k (the second inequality assumes the deepest level of the heap is full; if it's not, it should probably be something like 2^(h-d-1)-1 <= n-k instead).

In conclusion, the kth element can be pretty much anywhere between between depths max(2, h-log(n-k+1)) and min(k, h) where h is the height of the heap.