Heap Data Structure

Question

Trying to think about the lower border of a position, say, the n-th largest key in the max-heap. Suppose the heap is laid out in an array. The upper border is min (2 ^ n-2, array size is -1), I think, but is it always below 0?

Answer 1

An initial study of the problem shows the following relationship between n and the lower and upper bounds (the assumption consists of 14 elements in a 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 can be larger than the element at a specific location in the heap array, calculate the size of the subtree embedded at that location. These two numbers are then linked by the formula

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

EDIT: Please note that the calculation is performed in reverse order. Given the position in the array / heap, you can determine in which position this value will be if the heap has been sorted. Given node, the heap can be divided into three sections:

• Elements that are guaranteed to be larger than the current element (parent, parent parent, ...)
• Elements that are guaranteed to be smaller than the current element (subtree rooted in the current element)
• The remaining elements, which may be larger or smaller than the current element.

If we look at an approximate pile with 14 elements and want to determine the range of possible values ​​in 6th place, then the following groups:

• 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)

Therefore, the lower border is 3 (# elements in the group 1 + 1), and the upper border is 11 (# elements in the group 1 + # elements in the group 3 + 1).