如何在 1 到 n 个不同元素的最大堆中找到第三个最小元素的可能索引？我知道最小的元素会在叶子的任何地方。当 n 大于 3 时，第二小将在 n/2 到 n 之间，但我不知道要计算第三小。有什么建议么？
问问题
2728 次
1 回答
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)i2ki-2某个级别的后代小于kn - 2ki+1级别的后代k；总：
n-1子孙。
如果，则有：
n ≥ 2k(i+1) and n < 2k+1ii- 正是后代。
2k+1-1
- 正是后代。
粗略地说，这意味着在堆底层数组的第一部分中找不到最后一个元素。2k1/2k
于 2013-03-10T03:17:40.600 回答