Python cookbook（数据结构与算法）找到最大或最小的N个元素实现方法示例
本文实例讲述了python找到最大或最小的N个元素实现方法。分享给大家供大家参考，具体如下：
问题：想在某个集合中找出最大或最小的N个元素
解决方案：heapq模块中的nlargest()和nsmallest()两个函数正是我们需要的。
>>>importheapq >>>nums=[1,8,2,23,7,-4,18,23,42,37,2] >>>print(heapq.nlargest(3,nums)) [42,37,23] >>>print(heapq.nsmallest(3,nums)) [-4,1,2] >>>
这两个函数接受一个参数key，允许其工作在更复杂的数据结构之上：
#example.py
#
#ExampleofusingheapqtofindtheNsmallestorlargestitems
importheapq
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=lambdas:s['price'])
expensive=heapq.nlargest(3,portfolio,key=lambdas:s['price'])
print(cheap)
print(expensive)
Python3.4.0(v3.4.0:04f714765c13,Mar162014,19:24:06)[MSCv.160032bit(Intel)]onwin32
Type"copyright","credits"or"license()"formoreinformation.
>>>================================RESTART================================
>>>
[{'name':'YHOO','price':16.35,'shares':45},{'name':'FB','price':21.09,'shares':200},{'name':'HPQ','price':31.75,'shares':35}]
[{'name':'AAPL','price':543.22,'shares':50},{'name':'ACME','price':115.65,'shares':75},{'name':'IBM','price':91.1,'shares':100}]
>>>
如果正在寻找的最大或最小的N个元素，且相比于集合中元素的数量，N很小时，下面的函数性能更好。
这些函数首先会在底层将数据转化为列表，且元素会以堆的顺序排列。
>>>importheapq >>>nums=[1,8,2,23,7,-4,18,23,42,37,2] >>>heap=list(nums) >>>heap [1,8,2,23,7,-4,18,23,42,37,2] >>>heapq.heapify(heap)#heapify()参数必须是list，此函数将list变成堆，实时操作。从而能够在任何情况下使用堆的函数。 >>>heap [-4,2,1,23,7,2,18,23,42,37,8] >>>heapq.heappop(heap)#如下是为了找到第3小的元素 -4 >>>heapq.heappop(heap) 1 >>>heapq.heappop(heap) 2 >>>
堆（heap）最重要的特性就是heap[0]总是最小的元素。可通过heapq.heappop()轻松找到最小值，这个操作的复杂度为O(logN)，N代表堆得大小。
总结：
1、当要找的元素数量相对较小时，函数nlargest()和nsmallest()才最适用。
2、若只是想找到最小和最大值（N=1）时，使用min()和max()会更快。
3、若N和集合本身的大小差不多，更快的方法是先对集合排序再进行切片操作（例如使用sorted(items)[:N]或sorted(items)[-N：]）
4、heapq.heappush(heap,item):将item压入到堆数组heap中。如果不进行此步操作，后面的heappop()失效；
heapq.heappop(heap):从堆数组heap中取出最小的值，并返回。
heapq.heapify(list):参数必须是list，此函数将list变成堆，实时操作。从而能够在任何情况下使用堆的函数。
heapq.heappushpop(heap,item):是上述heappush和heappop的合体，同时完成两者的功能.注意：相当于先操作了heappush(heap,item),然后操作heappop(heap)
heapreplace(heap,item):是heappop(heap)和heappush(heap,item)的联合操作。注意，与heappushpop(heap,item)的区别在于，顺序不同，这里是先进行删除，后压入堆
heap,merge(*iterables)
>>>h=[]#定义一个list >>>fromheapqimport*#引入heapq模块 >>>h [] >>>heappush(h,5)#向堆中依次增加数值 >>>heappush(h,2) >>>heappush(h,3) >>>heappush(h,9) >>>h#h的值 [2,5,3,9] >>>heappop(h)#从h中删除最小的，并返回该值 2 >>>h [3,5,9] >>>h.append(1)#注意，如果不是压入堆中，而是通过append追加一个数值 >>>h#堆的函数并不能操作这个增加的数值，或者说它堆对来讲是不存在的 [3,5,9,1] >>>heappop(h)#从h中能够找到的最小值是3,而不是1 3 >>>heappush(h,2)#这时，不仅将2压入到堆内，而且1也进入了堆。 >>>h [1,2,9,5] >>>heappop(h)#操作对象已经包含了1 1
>>>h [1,2,9,5] >>>heappop(h) 1 >>>heappushpop(h,4)#增加4同时删除最小值2并返回该最小值，与下列操作等同： 2#heappush(h,4),heappop(h) >>>h [4,5,9]
>>>a=[3,6,1] >>>heapify(a)#将a变成堆之后，可以对其操作 >>>heappop(a) 1 >>>b=[4,2,5]#b不是堆，如果对其进行操作，显示结果如下 >>>heappop(b)#按照顺序，删除第一个数值并返回,不会从中挑选出最小的 4 >>>heapify(b)#变成堆之后，再操作 >>>heappop(b) 2
>>>a=[] >>>heapreplace(a,3)#如果list空，则报错 Traceback(mostrecentcalllast): File"",line1,in IndexError:indexoutofrange >>>heappush(a,3) >>>a [3] >>>heapreplace(a,2)#先执行删除（heappop(a)->3),再执行加入（heappush(a,2)) 3 >>>a [2] >>>heappush(a,5) >>>heappush(a,9) >>>heappush(a,4) >>>a [2,4,9,5] >>>heapreplace(a,6)#先从堆a中找出最小值并返回，然后加入6 2 >>>a [4,5,9,6] >>>heapreplace(a,1)#1是后来加入的，在1加入之前，a中的最小值是4 4 >>>a [1,5,9,6]
>>>a=[2,4,6] >>>b=[1,3,5] >>>c=merge(a,b) >>>list(c) [1,2,3,4,5,6]
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。