da-liang-shu-ju-zhong-zui-xiao-de-n-ge-shu.md

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

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

   199
   300
   21
   -9
   132
   8760
   7653
   ......
   

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

   现在我需要从这个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个数了。