用堆找出最小的 N 个数

不知道为啥，突然想水一篇很水的算法文章。 今天整理 MySQL 的笔记，看到了这样一句话： MySQL 在执行 ORDER BY x LIMIT n 这类语句，且 LIMIT 的数量有限时（比如只需要 3 条数据），MySQL 会尽量通过堆来构建优先队列，减少排序所需的时间。 这是堆的一个经典应用：从海量数据中找出最大（小）的 n 个数。 之前只用堆写过堆排，没有用堆处理过在线算法，所以就写了写。 用一句话概括这个算法：要找最小的数，就要构建大顶堆。 在处理数据时，我们会构建一个大顶堆 H，那么 H[0] 的值也就是当前数据中最小的 N 个数中的最大值，也就是第 N 小的数。 当处理新的数时，如果这个数小于堆顶的数，那么就把它变成堆顶，然后再对堆进行维护，以保证有序。 此算法的时间复杂度为 O(Ml..