Python cookbook（数据结构与算法）找到最大或最小的N个元素实现方法示例

概述本文实例讲述了python找到最大或最小的N个元素实现方法。分享给大家供大家参考，具体如下：

本文实例讲述了python找到最大或最小的N个元素实现方法。分享给大家供大家参考，具体如下：

问题：想在某个集合中找出最大或最小的N个元素

解决方案：heapq模块中的nlargest()和nsmallest()两个函数正是我们需要的。

>>> import heapq>>> nums=[1,8,2,23,7,-4,18,42,37,2]>>> print(heapq.nlargest(3,nums))[42,23]>>> print(heapq.nsmallest(3,nums))[-4,1,2]>>>

这两个函数接受一个参数key，允许其工作在更复杂的数据结构之上：

# example.py## Example of using heapq to find the N smallest or largest itemsimport heapqportfolio = [ {'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'])expensive = heapq.nlargest(3,key=lambda s: s['price'])print(cheap)print(expensive)

Python 3.4.0 (v3.4.0:04f714765c13,Mar 16 2014,19:24:06) [MSC v.1600 32 bit (Intel)] on win32Type "copyright","credits" or "license()" for more information.>>> ================================ RESTART ================================>>>[{'name': 'YHOO','price': 16.35,'shares': 45},'price': 21.09,'shares': 200},'price': 31.75,'shares': 35}][{'name': 'AAPL','price': 543.22,'shares': 50},'price': 115.65,'shares': 75},{'name': 'IBM','price': 91.1,'shares': 100}]>>>

如果正在寻找的最大或最小的N个元素，且相比于集合中元素的数量，N很小时，下面的函数性能更好。

这些函数首先会在底层将数据转化为列表，且元素会以堆的顺序排列。

>>> import heapq>>> nums=[1,2]>>> heap=List(nums)>>> heap[1,2]>>> heapq.heAPIfy(heap) #heAPIfy()参数必须是List，此函数将List变成堆，实时 *** 作。从而能够在任何情况下使用堆的函数。>>> heap[-4,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>>> from heapq import * #引入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,9]>>> h.append(1)   #注意，如果不是压入堆中，而是通过append追加一个数值>>> h    #堆的函数并不能 *** 作这个增加的数值，或者说它堆对来讲是不存在的[3,9,1]>>> heappop(h)   #从h中能够找到的最小值是3,而不是13>>> heappush(h,2)  #这时，不仅将2压入到堆内，而且1也进入了堆。>>> h[1,5]>>> heappop(h)   # *** 作对象已经包含了11

>>> h[1,5]>>> heappop(h)1>>> heappushpop(h,4)  #增加4同时删除最小值2并返回该最小值，与下列 *** 作等同：2    #heappush(h,4),heappop(h)>>> h[4,9]

>>> a=[3,6,1]>>> heAPIfy(a)   #将a变成堆之后，可以对其 *** 作>>> heappop(a)1>>> b=[4,5]   #b不是堆，如果对其进行 *** 作，显示结果如下>>> heappop(b)   #按照顺序，删除第一个数值并返回,不会从中挑选出最小的4>>> heAPIfy(b)   #变成堆之后，再 *** 作>>> heappop(b)2

>>> a=[]>>> heapreplace(a,3)  #如果List空，则报错Traceback (most recent call last):file "<stdin>",line 1,in <module>IndexError: index out of range>>> 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,5]>>> heapreplace(a,6)  #先从堆a中找出最小值并返回，然后加入62>>> a[4,6]>>> heapreplace(a,1)  #1是后来加入的，在1加入之前，a中的最小值是44>>> a[1,6]

>>> a=[2,6]>>> b=[1,5]>>> c=merge(a,b)>>> List(c)[1,6]

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码 *** 作技巧总结》、《Python函数使用技巧总结》、《Python字符串 *** 作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

您可能感兴趣的文章:Python数据结构与算法之字典树实现方法示例Python cookbook（数据结构与算法）字典相关计算问题示例Python cookbook（数据结构与算法）让字典保持有序的方法Python cookbook（数据结构与算法）在字典中将键映射到多个值上的方法Python 字典(Dictionary) *** 作详解python两种遍历字典(dict)的方法比较python提取字典key列表的方法Python中字典创建、遍历、添加等实用 *** 作技巧合集Python cookbook（数据结构与算法）保存最后N个元素的方法Python cookbook（数据结构与算法）从任意长度的可迭代对象中分解元素 *** 作示例Python cookbook（数据结构与算法）将序列分解为单独变量的方法Python cookbook（数据结构与算法）实现查找两个字典相同点的方法 总结

以上是内存溢出为你收集整理的Python cookbook（数据结构与算法）找到最大或最小的N个元素实现方法示例全部内容，希望文章能够帮你解决Python cookbook（数据结构与算法）找到最大或最小的N个元素实现方法示例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。