最大堆中第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發現。