binary-heap - 堆数据结构

Question

试图想出一个下界，比如最大堆中第 n 大键的位置。假设堆排列在数组中。我认为上限的 min(2^n-2, array size -1) 是否总是下限为 0？

Answer 1

对问题的初步调查揭示了 n 与上下界之间的以下关系(假设堆中有 14 个元素)

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

要确定可能大于堆数组特定位置的元素的数量，请计算以该位置为根的子树的大小。这两个数字然后通过公式相关

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

编辑:
请注意，计算是反向执行的。给定数组/堆中的位置，可以确定如果堆已排序，则该值将位于哪个位置。给定节点，堆可以分为三个分区:

保证大于当前元素的元素(父元素，父元素，...)

保证小于当前元素的元素(以当前元素为根的子树)

剩余元素可以大于或小于当前元素。

如果我们查看一个包含 14 个元素的示例堆，并且想要确定第 6 个位置中可能值的范围，则这些组如下:

第 1 组包含两个元素 (3, 1)

第 2 组包含两个元素 (12, 13)

第 3 组包含其余九个元素(不包括当前值)(2, 4, 5, 7, 8, 9, 10, 11, 14)

因此，下限是 3(第一组元素的数量 + 1)，而上限是 11(第一组元素的数量 + 第三组元素的数量 + 1)。