binary-heap - 堆数据结构

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

最佳答案

对问题的初步调查揭示了 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 组包含剩余的 9 个元素(不包括当前值)(2, 4, 5, 7, 8, 9, 10, 11, 14)

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

关于binary-heap - 堆数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2492884/