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

Question

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

Answer 1

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

正如您几乎注意到的那样，叶子的索引范围为[floor(n/2)+1, n]。如果n/2是整数，则该元素只有一个子元素（即叶子），因此添加它会给出可能包含第二大元素的索引范围。

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

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

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

---

这是另一种方法。在 index 处取一些元素i。它的直系孩子是2iand 2i+1; 它的孙子是4i, 4i+1, 4i+2, 4i+3，一般来说，它的后代k是；总之，。当然，这些范围是不重叠的（实际上，除非is ，它们甚至都不连续）。所以如果在一个层次上至少有一个后代，那么它也有一套完整的后代，其中有。2ki, 2ki+1, ..., 2ki + 2ki-1[2ki, ..., 2k(i+1)-1 ]i1ikk' < k2k-2

综上所述，我们可以得出结论：

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

  • 2ki-2某个级别的后代小于k

  • n - 2ki+1级别的后代k；

  • 总：n-1子孙。

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

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

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