Python实现从实现从N个数中找到最大的个数中找到最大的K个数个数
提出问题：提出问题：
如何在某集合里面找出最大或最小的K个元素。
解决思路：解决思路：
找出最大或最下的K个元素，可以使用Python库中的heapq模块，该模块提供两个函数nlargest()求最大K个和nsmallest()求最
小K个。
下面我们举例说明：下面我们举例说明：
import heapq
nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq.nlargest(4,nums)) #-->最大的4个
print(heapq.nsmallest(4,nums)) #-->最小的4个
运行结果：
[56, 34, 32, 23] [-9, -3, 0, 9]
分析下，nlargest()和nsmallest()函数有两个参数，第一个参数是求最大或最下的K个元素，第二个参数是待查询的集合。除此
之外，他们也可以接受一个参数key，这使得他们处理更加复杂的数据结构。例如：
import heapq
portfolio = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
print(cheap)
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
print(expensive)
运行结果：
[{‘name’: ‘YHOO’, ‘shares’: 45, ‘price’: 16.35}, {‘name’: ‘FB’, ‘shares’: 200, ‘price’: 21.09}, {‘name’: ‘HPQ’, ‘shares’:
35, ‘price’: 31.75}] [{‘name’: ‘AAPL’, ‘shares’: 50, ‘price’: 543.22}, {‘name’: ‘ACME’, ‘shares’: 75, ‘price’: 115.65},
{‘name’: ‘IBM’, ‘shares’: 100, ‘price’: 91.1}]
深入讨论：深入讨论：
假如说，我们正在寻找某集合中最大或最下的K个元素，并且N的数值很小，如果再使用上面的方法，可能就不是最好的选
择。那么，我们介绍heapify()函数，这个函数首先会在底层将数据转换成列表，并且元素会以堆的顺序排列。举例：
从上面的代码中，我们看出元素确实是以堆的顺序排列的，同时堆hea_num[0]对应的元素-9总是最小的。在heapq（）模块中
还提供heappop()函数，该方法会把第一个元素（最小的）给弹出来，然后第二小的元素会自动补位，它的操作时间复杂度是
O(log N),其中N代表的是堆的大小。
具体的操作看下面的代码：
评论0