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

Question

如何找到最大堆中1到n个不同元素中第3个最小元素的可能索引？ 我知道最小的元素会在树叶中的任何地方。 第二小的将是从n/2到n的任何地方，大于3的时候n 但我不知道要计算第三小的值。有什么建议么？

Answer 1

第三小元素至多有两个后代，这意味着它的子（ren）是叶子，或者它是叶子。 （为了证明这一点，你还必须证明，一个只有一个孩子的元素不可能有一个非叶子作为孩子。简单但乏味）

叶子，你几乎注意到，范围为[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是2ki, 2ki+1, ..., 2ki + 2ki-1;总之，[2ki, ..., 2k(i+1)-1 ]。这些范围当然是不重叠的（实际上，除非i是1，它们甚至不是连续的）。所以如果i至少有一个在k级别的后裔，它也有一整套k' < k的后裔，其中有2k-2。

从所有这一切，我们可以得出结论：

• 如果n ≥ 2ki and n < 2k(i+1)，然后i有：

  • 2ki-2后裔在一定程度上在k水平低于k

  • n - 2ki+1后裔;

  • 总计：n-1后代。

• 如果n ≥ 2k(i+1) and n < 2k+1i，然后i有：

  • 正是2k+1-1后裔。

粗略地说，这意味着最后2k元件没有在堆中的底层阵列的所述第一部分1/2k发现。