其他

这里总结一些有趣的“小”算法。

最少比较次数找到第二大数

给定数组包含 $n$ 个不同的数，简单起见，$n$ 是 2 的幂次。如何能够最多比较 $n+\log_2 n-2$ 得到第二大数？

构建一个败者树，类似于世界杯决赛圈，两两一组，赢的晋级，然后再两两一组比较，最终有一个胜利者。这个胜利者就是最大的数，这里需要 $n-1$ 次比较。

在整个比赛过程中，第二大的数字一定是被最大的数字击败了，最大数共计击败了 $\log_2 n$ 个数，从这里面找到最大的数，就是第二大的数字，这里需要 $\log_2 n-1$ 次比较。

共计需要比较 $n+\log_2 n-2$ 次比较。

中位数

给定一个数字流，要求其任意时刻的中位数。

构建两个堆，$H_1,H_2$，前者是大堆，后者是小堆，两个堆始终满足两个属性：一是大堆最大的元素小于等于小堆最小元素，二是两个堆的元素数量最多差一。

如果两个堆的元素个数相同，那么中位数是任意一个堆的堆顶，如果两个堆的元素个数差一，那么中位数是元素个数多的堆的堆顶。

假定要插入的元素是 $x$，$H_1,H_2$ 的堆顶分别是 $y,z$。插入元素的过程如下所述。

如果 $x<y$，插入 $H_1$，如果 $x>z$，插入 $H_2$。如果插入前两个堆元素个数相等，那么可以直接插入，如果元素个数差一并且插入后元素个数差二，从多的堆中往少的堆中挪一个元素保持平衡。如果 $y<x<z$，那么可以插入哪个堆都是可以的。如果插入前两个堆元素个数相等，随便选择一个堆即可，如果元素个数差一，那么选择元素个数少的堆以保持平衡。