Heap data structure

Question

Trying to think of a lower bound to the position of say, the nth largest key in a max-heap. Assuming the heap's laid out in array. The upper bound's min(2^n-2, array size -1) i think, but is it always lower bounded by 0?

Answer 1

Initial investigation of the problem reveals the following relation between n and the lower and upper bounds (assumption there are 14 elements in the heap)

n   lb  up
1   1   1
2   2   3
3   2   7
4   2   14
9   3   14
10  4   14
12  5   14
13  6   14
14  8   14

To determine the number of elements that are possible larger than the element in a specific location of the heap array, calculate the size of the subtree rooted at that location. These two numbers are then related by the formula

# of elements possible larger  = total number of elements - size of subtree - 1 

EDIT: Note that the calculation is performed backwards. Given a position in the array / heap, it is possible to determine in which position the value will be if the heap were sorted. Given the node the heap can be divided into three partitions:

1. Elements that are guaranteed to be larger than the current element (the parent, the parents parent, ...)
2. Elements that are guaranteed to be smaller than the current element (the subtree rooted at the current element)
3. The remaining elements which can be either larger or smaller than the current element.

If we look at an example heap with 14 elements and want to determine the range of possible values in the 6th location, the groups are as follows:

• Group 1 contains two elements (3, 1)
• Group 2 contains two elements (12, 13)
• Group 3 contains the remaining nine elements (excluding the current value) (2, 4, 5, 7, 8, 9, 10, 11, 14)

The lower bound is therefore 3 (# of elements in group one + 1) while the upper bound is 11 (# of elements in group one + # of elements in group three + 1).