python3-开发进阶 heapq模块(如何查找最大或最小的N个元素)
2024-10-21 03:01:01
一、怎样从一个集合中获得最大或者最小的 N 个元素列表?
heapq 模块有两个函数:nlargest() 和 nsmallest() 可以完美解决这个问题。
import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2] #前面的参数可选多个元素
两个函数都能接受一个关键字参数,用于更复杂的数据结构中:
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'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
PS:上面代码在对每个元素进行对比的时候,会以 price 的值进行比较。
二、如何查找最大或最小的 N 个元素
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
import heapq
heapq.heapify(nums)
print(nums)
#[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
堆数据结构最重要的特征是 heap[0] 永远是最小的元素。并且剩余的元素可以很
容易的通过调用 heapq.heappop() 方法得到,该方法会先将第一个元素弹出来,然后
用下一个最小的元素来取代被弹出元素 (这种操作时间复杂度仅仅是 O(log N),N 是
堆大小)。
如果想要查找最小的 3 个元素,你可以这样做:
heapq.heappop(nums)
#-4
heapq.heappop(nums)
#1
heapq.heappop(nums)
#2
当要查找的元素个数相对比较小的时候,函数 nlargest() 和 nsmallest() 是很
合适的。如果你仅仅想查找唯一的最小或最大 (N=1) 的元素的话,那么使用 min() 和
max() 函数会更快些。类似的,如果 N 的大小和集合大小接近的时候,通常先排序这
个集合然后再使用切片操作会更快点 ( sorted(items)[:N] 或者是 sorted(items)[-
N:] )。需要在正确场合使用函数 nlargest() 和 nsmallest() 才能发挥它们的优势 (如果
N 快接近集合大小了,那么使用排序操作会更好些)
三、实现一个优先级队列
怎样实现一个按优先级排序的队列?并且在这个队列上面每次 pop 操作总是返回
优先级最高的那个元素
下面的类利用 heapq 模块实现了一个简单的优先级队列:
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
下面是使用方法:
>>> class Item:
... def __init__(self, name):
... self.name = name
... def __repr__(self):
... return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
仔细观察可以发现,第一个 pop() 操作返回优先级最高的元素。另外注意到如果
两个有着相同优先级的元素 ( foo 和 grok ),pop 操作按照它们被插入到队列的顺序返
回的。
最新文章
- oracle sql别名
- 新建maven项目
- August 4th, 2016, Week 32nd, Thursday
- for xml path('') 引发的数据不完整
- Openstack REST API
- Cocos2d-x 创建自己定义项目模板
- android之IntentFilter的用法_Intent.ACTION_TIME_TICK在manifest.xml不起作用
- jquery uploadifive使用
- JMETER 不同线程组 变量值 的参数传递
- 【Socket编程】Java中网络相关API的应用
- [LeetCode] My Calendar III 我的日历之三
- java.lang.AbstractMethodError: org.mybatis.spring.transaction.SpringManagedTransaction.getTimeout()Ljava/lang/Integer; 报错解决
- 学习java一个月的进展
- 导入tensorflow时DLL load failed: 找不到指定的模块
- Dubbo 的配置主要分为三大类
- adb错误处理
- 判断np.array里面为空字符串的方法
- Redis 应该是存放的数据超出了范围
- C语言程序设计I—第九周教学
- Python学习---Model拾遗[1]180318
热门文章
- 448D - Codeforces
- Linux内核模块编程可以使用的内核组件
- 【bzoj3545】peaks
- 2017中国大学生程序设计竞赛 - 网络选拔赛 HDU 6152 Friend-Graph 暴暴暴暴力
- swift中的如果在构造方法中使用KVC, 调用了super.init(), 报错, 基本数据类型属性找不到
- 辨别苹果数据线真伪 苹果计算器 Dashboard 知识
- network-scoket
- 流程控制--for序列
- BlockingQueue drainTo()
- [转]windows消息机制(MFC)