最大堆中第三小元素的索引

Question

最大堆中第三小元素的索引

3

如何在1到n个不同元素的最大堆中找到第三小的元素可能的索引？我知道最小的元素会在叶子节点中。当n大于3时，第二小的元素将在n/2到n的任何位置。但我不知道如何计算第三小的元素。有什么建议吗？

- chotu123

在一个真正的二叉最大堆中，如果我正确地回忆起我的数据结构，最小的(n+1)/2个节点将是叶子节点。因此，你的第三个最小值将是这些节点之一，或者是其中一个节点的直接父节点。即使假设堆已经完全建立，我也无法想象出一种能够在O(1)时间内提取该值的闭式算法。 - WhozCraig

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

第三小的元素最多有两个子节点，这意味着它的子节点是叶子或者它本身就是叶子。（为了证明这一点，您还需要证明只有一个子节点的元素不可能有一个非叶子节点作为子节点。容易但繁琐。）

叶子节点的索引在范围内[ floor(n/2)+1 , n ]。如果n/2是整数，则该元素恰好有一个子节点（即叶子），因此加上它将给出可能包含第二大元素的索引范围。

第一个子节点位于叶子范围 [ floor(n/2)+1 , n ] 的元素最多有两个子节点，并且没有非叶子子节点。该范围与 [ ceil(n/2) , n ] 范围相邻，两个范围的并集提供了第三大元素的所有可能位置。

元素 i 的第一个子节点的索引为 2i，因此第一个子节点至少为 floor(n/2)+1 的元素是 floor(n/4)+1。

因此，您可以找到第三大的元素的可能索引范围为：[floor(n/4)+1,n]。

这里有另一种方法。取一个索引为i的元素。它的直接子元素是2i和2i+1；它的孙子元素是4i, 4i+1, 4i+2, 4i+3，通常情况下，它在级别k的后代是2^ki, 2^ki+1, ..., 2^ki + 2^ki-1, 简而言之，是[2^ki, ..., 2^k(i+1)-1 ]。当然，这些范围是不重叠的（实际上，除非i是1，否则它们甚至不是连续的）。因此，如果i至少有一个级别为k的后代，则它也具有所有k' < k的完整后代集合，其中有2^k-2个。

从所有这些中，我们可以得出结论：

如果 n ≥ 2^ki 且 n < 2^k(i+1)，那么 i 具有：
- 2^ki-2 个后代在某个水平小于 k 的级别上
- n - 2^ki+1 个后代在水平 k 上;
- 总计: n-1 个后代。
如果 n ≥ 2^k(i+1) 且 n < 2^k+1i，那么 i 具有：
- 恰好 2^k+1-1 个后代。

粗略地讲，这意味着堆的底层数组的前 1/2^k 部分中找不到最后的 2^k 个元素。