3.4　查找最大或最小的N个元素

从一个集合中获取最大或最小的元素比较简单，但若要获得最大或者最小的N个元素，是否有直接可以使用的函数？

heapq模块中有两个函数可以非常好地解决这个问题。这两个函数分别是nlargest()和nsmallest()，使用示例如下：

import heapq
num_list = [1, 33, 3, 18, 7, -5, 18, 33, 51, -60, 5]
print(heapq.nlargest(3, num_list))
print(heapq.nsmallest(3, num_list))

这两个函数不但可以用于处理关键字参数，还可以用于处理更复杂的数据结构，示例如下：

import heapq
offer_dict = [
    {'company_name': 'IBM', 'stock': 80, 'price': 81.1},
    {'company_name': 'AAPL', 'stock': 60, 'price': 113.22},
    {'company_name': 'FB', 'stock': 150, 'price': 91.09},
    {'company_name': 'HPQ', 'stock': 30, 'price': 79.75},
    {'company_name': 'YHOO', 'stock': 50, 'price': 85.35},
    {'company_name': 'ACME', 'stock': 100, 'price': 76.65}
    ]
    cheapest = heapq.nsmallest(3, offer_dict, key=lambda s: s['price'])
    max_stock = heapq.nlargest(2, offer_dict, key=lambda s: s['stock'])

上述代码段在对每个元素进行对比时，cheapest会以price值进行比较，找出price值最小的3个记录；max_stock会以stock值进行比较，找出stock值最大的2个记录。

在heapq模块的底层实现中，首先会将集合数据进行堆排序，然后放入一个列表中。如果想在一个集合中查找最小或最大的N个元素，并且N小于集合元素数量，那么heapq模块中的函数具有很好的性能。

堆数据结构最重要的特征是heap[0]永远是最小的元素，并且剩余的元素可以很容易地通过调用heapq.heappop()方法得到。heapq.heappop()方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素（这种操作的时间复杂度仅仅是O(logN)，N是堆大小）。如要查找最小的3个元素，执行3次heapq.heappop()即可。

当要查找的元素个数相对比较小的时候，函数nlargest()和nsmallest()是很合适的。如果仅仅想查找唯一的最小或最大（N=1）的元素，那么使用min()和max()函数会更快些。类似地，如果N的大小和集合大小接近，通常先排序集合元素，然后再使用切片操作（sorted(items)[:N]或者是sorted(items)[-N:]），这样运行速度会更快点。

nlargest()和nsmallest()函数需要用在正确场合才能发挥优势（如果N接近集合大小，那么使用排序操作会更好些）。