如何用最少的比较次数找出数组中第二小的元素？

[hushicai]

原文地址：https://www.geeksforgeeks.org/second-minimum-element-using-minimum-comparisons/

[hushicai]

从寻找最小数出发，构建一棵胜者树，根节点即为最小数。

此时胜者树中已经包含了一个隐藏的信息：最小数必然已经和第二小数比较过了！

所以我们只需要从根节点出发，沿着最小数路径进行遍历，并用另一边子树根节点更新第二小数，最后达到叶子节点，即可得到第二小数。

寻找最小数需要 n-1 次比较。

遍历平衡二叉树需要 logn - 1 次比较。

总的时间复杂度 (n - 1) + (logn - 1) = n + logn - 2。

[hushicai]

寻找最小数的过程，可以看作一个只有0度和2度节点的胜者树，叶子节点就是原始的输入，根节点就是最后的最小数，每个2度节点都代表一次比较。

根据这种只有0度和2度节点树的特性，内部节点刚好有n-1个，所以获得最小数需要 n-1 次操作。

第二小数有一个性质：它一定与最小数比较过，且是所有与最小数比较过的数中的最小数。

为了得到第二小数，我们只需要收集胜者树中最小数路径上所有的兄弟节点，并再次调用一次最小数算法，即可得到第二小数。

由于当前胜者树的形状，最小数的所有兄弟节点个数不会超过logn，所以得到第二小数的比较次数不会超过 logn - 1。

因此，我们可以在 n + logn - 2 次比较内得到第二小数。