在n + 2k-3比较中找出大小为（2^k +1）的第三大元素

Question

“在n + 2k-3个比较中查找大小为（2^k + 1）的第三大元素“。

这是一个我在算法课程期末考试中遇到的问题，我没有得到所有要点。我不知道彻底的互联网搜索后，什么是正确的答案。

我意识到这是第二大问题的扩展版本，但所要求的严格比较界限使问题变得棘手。 我也找到了一个数学解释来找到第K个元素here，但是这对我来说太复杂了。

表示数组大小为n = 2^K + 1

在考试本身我的回答是这样的：

我们将使用一个比赛树。首先，我们排除了任意的因素。
然后建立由2^k个元素组成的树。因此树中有K个级别（log（2^k））。

找到胜利者将带我们进行n-2次比较。

寻找失败者中最大的元素。 （K-1 comp。）

找到输给决赛输家的人中最大的一个。 （K-2 comp。）

我们将比较这些和我们在开始时忽略的一个。 （2 comp。）

3中最大的一个是阵列中的第3大。

总的比较：N - 2 + K - 1 + K - 2 + 2 = N + 2K - 3

我得到了10分满分的25

我已经做了2次失误。主要的是如果期望的元素在赢家的子树中，我的回答将是不正确的。此外，正确的答案应该是我最后比较的3我中的第二大。

另一种算法，我发现如下：
- 建材锦标赛树和寻找赢家（N - 2）
所有失败者比较的赢家-Finding第二位。 （也可以通过锦标赛树）（k - 1）
- 答案在最大的输家中排名第二，输家在第一棵树中输了。 （log（k + 1）+ K-1-1）

- 此解决方案假定我们省略的元素不是数组中最大的元素。如果是这样，我不确定它的行为。 另外，我可能没有正确理解比较的数量。

我很乐意看看是否有更好的解释算法。 我也很想知道是否有更多的第L个最大（K被采取..）。

由于提前， 伊泰

Answer 1

1. 构造n个比赛树 - 1 = 2 ^{k中的元素的}，任意选择。 （n - 2比较）

2. 在叶子处，用未选择的元素替换所选元素的最大值。重建锦标赛树。 （k次比较）

3. 取最大值丢失到新的最大值，如第二大算法。 （k - 1比较）

我会留下正确性证明作为练习。