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 

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

1. 保证大于当前元素的元素（父元素、父元素、父元素……）
2. 保证小于当前元素的元素（以当前元素为根的子树）
3. 其余元素可以大于或小于当前元素。

如果我们看一个有 14 个元素的示例堆，并且想要确定第 6 个位置的可能值的范围，则组如下：

• 第 1 组包含两个元素 (3, 1)
• 第 2 组包含两个元素 (12, 13)
• 第 3 组包含其余九个元素（不包括当前值）（2、4、5、7、8、9、10、11、14）

因此，下限为 3（第一组中的元素数量 + 1），而上限为 11（第一组中的元素数量 + 第三组中的元素数量 + 1）。