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

Question

我如何找到 1 到 n 个不同元素的最大堆中第三小元素的可能索引？我知道最小的元素会出现在叶子的任何地方。对于大于 3 的 n，第二小的将在 n/2 到 n 之间的任何地方但我不知道要计算第三小。有什么建议吗？

Answer 1

第三小的元素最多有两个后代，也就是说它的child(ren)是叶子，或者它是一片叶子。 (为了证明这一点，你还必须证明只有一个 child 的元素不可能有一个非叶子作为 child 。简单但乏味。)

正如您几乎注意到的那样，叶子的索引在 [floor(n/2)+1, n] 范围内.如果n/2是一个整数，那么该元素恰好有一个子元素(它是一片叶子)，因此相加得到可能包含第二大元素的索引范围。

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

i 处元素的第一个子元素有索引2i , 因此第一个子元素至少为 floor(n/2)+1 的第一个元素是floor(n/4)+1 .

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

---

这是另一种方法。在索引 i 处取一些元素.它的直接 child 是 2i和 2i+1 ;它的孙子是4i, 4i+1, 4i+2, 4i+3而且，一般来说，它是级别 k 的后代是2<sup>k</sup>i, 2<sup>k</sup>i+1, ..., 2<sup>k</sup>i + 2<sup>k</sup>i-1 ;总之，[2<sup>k</sup>i, ..., 2<sup>k</sup>(i+1)-1 ] .当然，这些范围是不重叠的(实际上，除非 i 是 1 ，否则它们甚至不连续)。所以如果i在 k 层至少有一个后代, 它也有所有 k' < k 的完整后代集, 其中有 2<sup>k</sup>-2 .

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

• 如果 n ≥ 2<sup>k</sup>i and n < 2<sup>k</sup>(i+1) , 然后 i有:

  • 2<sup>k</sup>i-2某个级别的后代小于 k

  • n - 2<sup>k</sup>i+1级别 k 的后代;

  • 总计:n-1后代。

• 如果 n ≥ 2<sup>k</sup>(i+1) and n < 2<sup>k+1</sup>i , 然后 i有:

  • 正是2<sup>k+1</sup>-1后代。

粗略地说，这意味着最后一个 2<sup>k</sup>在第一个 1/2<sup>k</sup> 中找不到元素堆的底层数组的一部分。