本文最后更新于:2024年5月7日 下午
本文记录 Python 内置实现的小顶堆模块。
堆
- 堆是一种特殊的树,它每个结点都有一个值,堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆。就类似一堆东西一样,按照由大到小(或由小到大)“堆”起来。
- 此种数据结构适用于在经常变化、更新的序列中,需要时刻维护最小 / 最大值的情况
- 插入新元素或 pop 堆顶元素后重新维护堆结构的时间复杂度为 $O(logn)$
Python 内置 heapq
-
官方文档: https://docs.python.org/3/library/heapq.html#module-heapq
-
该模块提供了堆队列算法的实现,也称为优先队列算法。
-
Python 内置的堆将数据放在下标从0开始的序列中,并且使用
小顶堆
结构,因此 heap[0] 是最小的值,同时 heap.sort() 不会改变堆。
使用方法
创建堆
heapq.heapify(x)
- 堆是在已经存在的列表基础上创建的,需要先创建列表
x
,采用heapq.heapify(x)
将列表转化为堆
1 |
|
添加元素
heapq.heappush(heap, item)
- 将值项推送到堆上,保持堆不变。
弹出元素
heapq.heappop(heap)
- 从堆中弹出并返回最小的项目,保持堆不变。如果堆为空,则会引发 IndexError。
- 要访问最小的项目而不弹出它,请使用 heap[0]。
添加-弹出元素
heapq.heappushpop(heap, item)
- 添加元素的同时弹出堆顶元素,合并操作比两个单独操作效率高(实现上先添加元素后弹出元素)。
替换元素
heapq.heapreplace(heap, item)
- 从堆中弹出并返回最小的项目,并推送新项目。堆大小不会改变。如果堆为空,则会引发 IndexError。
- 该操作比两个单独操作效率高(实现上先弹出元素后添加元素),过程中size 不变,适合尺寸固定的堆。
- 由于先弹出后添加,因此返回的值可能大于添加的项目。如果不想要这种情况,请考虑使用 heappushpop() 代替。它的 push/pop 组合返回两个值中较小的一个,将较大的值留在堆上。
合并堆
heapq.merge(*iterables, key=None, reverse=False)
- 将多个排序的输入合并到一个排序的输出中。返回排序值的迭代器。
- reverse 是一个布尔值。如果设置为 True,则合并输入元素,就好像每次比较都颠倒了一样。要实现类似于
sorted(itertools.chain(*iterables), reverse=True)
的行为,所有可迭代对象必须从大到小排序。
第 n 大元素
heapq.nlargest(n, iterable, key=None)
- 从 iterable 定义的数据集中返回一个包含 n 个最大元素的列表。 key,如果提供,指定一个参数的函数,用于从 iterable 中的每个元素中提取比较键(例如,key=str.lower)。等价于:
sorted(iterable, key=key, reverse=True)[:n]
。
第 n 小元素
heapq.nsmallest(n, iterable, key=None)
- 从 iterable 定义的数据集中返回一个包含 n 个最小元素的列表。 key,如果提供,指定一个参数的函数,用于从 iterable 中的每个元素中提取比较键(例如,key=str.lower)。等价于:
sorted(iterable, key=key)[:n]
。
参考资料
- https://docs.python.org/3/library/heapq.html#module-heapq
- https://blog.csdn.net/lifei128/article/details/82392940
文章链接:
https://www.zywvvd.com/notes/coding/python/python-heap/python-heap/
“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”
微信支付
支付宝支付
Python 堆
https://www.zywvvd.com/notes/coding/python/python-heap/python-heap/