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接近集合大小，那么使用排序操作會更好些）。