数为分析例子，以便统一。注：本文写得会比较细节一些，以便于绝大多数人都能看懂，别嫌我罗嗦:) 我
很不确定多少人有耐心看完本文！
Naive 方法：
首先，我们假设 n 和 N 都是内存可容纳的，也就是说 N 个数可以一次 load 到内存里存放在数组里（如
果非要存在链表估计又是另一个 challenging 的问题了）。从最简单的情况开始，如果 n=1，那么没有任何疑
惑，必须要进行 N-1 次的比较才能得到最大的那个数，直接遍历 N 个数就可以了。如果 n=2 呢？当然，可
以直接遍历 2 遍 N 数组，第一遍得到最大数 max1，但是在遍历第二遍求第二大数 max2 的时候，每次都要
判断从 N 所取的元素的下标不等于 max1 的下标，这样会大大增加比较次数。对此有一个解决办法，可以
以 max1 为分割点将 N 数组分成前后两部分，然后分别遍历这两部分得到两个“最大数”，然后二者取一得
到 max2。
也可以遍历一遍就解决此问题，首先维护两个元素 max1，max2（max1>=max2），取到 N 中的一个数
以后，先和 max1 比，如果比 max1 大（则肯定比 max2 大），直接替换 max1，否则再和 max2 比较确定是
否替换 max2。采用类似的方法，对于 n=2，3，4„„一样可以处理。这样的算法时间复杂度为 O（nN）。
当 n 越来越大的时候（不可能超过 N/2，否则可以变成是找 N-n 个最小的数的对偶问题），这个算法的效率
会越来越差。但是在 n 比较小的时候（具体多小不好说），这个算法由于简单，不存在递归调用等系统损耗，
?
堆：
当 n 较大的时候采用什么算法呢？首先我们分析上面的算法，当从 N 中取出一个新的数 m 的时候，它
需要依次和 max1，max2，max3„„max n 比较，一直找到一个比 m 小的 max x，就用 m 来替换 max x，平
均比较次数是 n/2。可不可以用更少的比较次数来实现替换呢？最直观的方法是，也就是网上文章比较推崇
的堆。堆有这么一些好处：1.它是一个完全二叉树，树的深度是相同节点的二叉树中最少的，维护效率较
高；2.它可以通过数组来实现，而且父节点 p 与左右子节 l，r 点的数组下标的关系是 s[l] = 2*s[p]+1 和 s[r] =
2*s[p]+2。在计算机中 2*s[p]这样的运算可以用一个左移 1 位操作来实现，十分高效。再加上数组可以随机
存取，效率也很高。3.堆的 Extract 操作，也就是将堆顶拿走并重新维护堆的时间复杂度是 O（logn），这里
n 是堆的大小。
具体到我们的问题，如何具体实现呢？首先开辟一个大小为 n 的数组区 A，从 N 中读入 n 个数填入到
A 中，然后将 A 维护成一个小顶堆（即堆顶 A[0]中存放的是 A 中最小的数）。然后从 N 中取出下一个数，
即第 n+1 个数 m，将 m 与堆顶 A[0]比较，如果 m<=A[0]，直接丢弃 m。否则应该用 m 替换 A[0]。但此时
A 的堆特性可能已被破坏，应该重新维护堆：从 A[0]开始，将 A[0]与左右子节点分别比较（特别注意，这
里需要比较“两次”才能确定最大数，在后面我会根据这个来和“败者树”比较），如果 A[0]比左右子节点
都小，则堆特性能够保证，勿需继续，否则如左（右）节点最大，则将 A[0]与左（右）节点交换，并继续
维护左（右）子树。依次执行，直到遍历完 N，堆中保留的 n 个数就是 N 中最大的 n 个数。这都是堆排序
的基本知识，唯一的 trick 就是维护一个小顶堆，而不是大顶堆。不明白的稍微想一下。维护一次堆的时间
复杂度为 O（logn），总体的复杂度是 O（Nlogn）这样一来，比起上面的 O（nN），当 n 足够大时，堆的效
率肯定是要高一些的。当然，直接对 N 数组建堆，然后提取 n 次堆顶就能得到结果，而且其复杂度是 O（nlogN）,
当 n 不是特别小的时候这样会快很多。但是对于 online 数据就没办法了，比如 N 不能一次 load 进内存，甚
至是一个流，根本不知道 N 是多少。
败者树：
有没有别的算法呢？我先来说一说败者树（loser tree）。也许有些人对 loser tree 不是很了解，其实它是
一个比较经典的外部排序方法，也就是有 x 个已经排序好的文件，将其归并为一个有序序列。败者树的思
想咋一看有些绕，其实是为了减小比较次数。首先简单介绍一下败者树：败者树的叶子节点是数据节点，
然后两两分组（如果节点总数不是 2 的幂，可以用类似完全树的结构构成树），内部节点用来记录左右子树
的优胜者中的“败者”（注意记录的是输的那一方），而优胜者则往上传递继续比较，一直到根节点。如果
我们的优胜者是两个数中较小的数，则根节点记录的是最后一次比较中的“败者”，也就是所有叶子节点中
第二小的那个数，而最小的那个数记录在一个独立的变量中。这里要注意，内部节点不但要记录败者的数
值，还要记录对应的叶子节点。如果是用链表构成的树，则内部节点需要有指针指向叶子节点。这里可以
有一个 trick，就是内部节点只记录“败者”对应的叶子节点，具体的数值可以在需要的时候间接访问（这
一方法在用数组来实现败者树时十分有用，后面我会讲到）。关键的来了，当把最小值输出后，最小值所对
应的叶子节点需要变成一个新的数（或者改为无穷大，在文件归并的时候表示文件已读完）。接下来维护败
者树，从更新的叶子节点网上，依次与内部节点比较，将“败者”更新，胜者往上继续比较。由于更新节
点占用的是之前的最小值的叶子节点，它往上一直到根节点的路径与之前的最小值的路径是完全相同的。
内部节点记录的“败者”虽然称为“败者”，但却是其所在子树中最小的数。也就是说，只要与“败者”比
评论2