堆数据结构

Question

尝试考虑最大堆中第 n 个最大键的位置的下限。假设堆按数组排列。我认为上限是 min(2^n-2, 数组大小 -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 组包含剩余的 9 个元素（不包括当前值）（2, 4, 5, 7, 8, 9, 10, 11, 14），

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