一日一技：小内存使用最小堆从大量数据中寻找最小的N个数

如今，我们的硬盘空间远远大于内存。所以很容易出现硬盘中放得下的数据，在内存中放不下的情况。

现在我们有一个100GB的文本文件，它的内容如下：

19930021-913287607653......

每一行是一个数字。这些数字是没有顺序的。

现在我需要从这个100GB的文件里面，找到最大的100个数字。电脑内存为1GB。

由于内存非常小，因此不可能把全部数据读入内存，先排序再取最大的100个数。那么我们就需要边读文件边排序，并始终保留最大的100个数字。

肯定有同学会想到使用列表来解决这个问题。维护一个长度为100的列表，如果列表不满100，就把新来的数字加入进去；如果列表已经满了100，那么如果这个新来的数字小于列表里面的最小值，就直接丢弃；如果大于列表里面的最小值，那么就把原来的最小值丢弃，把新的数字插入进去。

这篇文章里面，我们将会使用上一篇文章讲到的 heapq来实现这个目的。

Python的 heapq实现的是一个最小堆，最小堆有如下性质：

1. 根节点始终是最小的
2. 最小堆是完全二叉树
3. 每个节点的两个子节点都不会比它小

所以，我们只需要维护一个有100个节点的最小堆即可。

那么代码如下：

import heapq
with open('100GBfile.txt', encoding='utf-8') as f:    heap = []    for num_str in f:        num = int(num_str)        if len(heap) < 100:            heapq.heappush(heap, num)        else:            if num > heap[0]:                heapq.heapreplace(heap, num)print(f'最大的100个数为：{heap}')

在Python 3里面，文件句柄f是一个生成器，对它使用for循环迭代，可以一行一行读取文件的内容。文本文件读出来的内容一定是字符串，所以需要使用 int(num)转换为数字。如果堆的节点数不够100，那么直接把数字插入堆里即可，heapq会自动决定这个数字在堆里面的位置。

由于最小堆的根节点一定是最小值，所以只需要比较新来的数字与根节点的大小即可，当新来的数字比根节点大时，就移除根节点，把它加入堆里面，然后heapq会自动跳转堆的结果，使这个堆仍然是最小堆。

当循环把大文件全部读完以后，堆里面的100个数字就是最大的100个数了。