Python 堆

本文最后更新于:2022年7月6日 下午

本文记录 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
2
3
4
5
6
7
8
import heapq

a = [9,3,5, 8, 2, 13, 7, 1, 2, 24]
heapq.heapify(a)
print(a)

-->
[1, 2, 5, 2, 9, 13, 7, 8, 3, 24]
添加元素
  • 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]

参考资料


Python 堆
https://www.zywvvd.com/notes/coding/python/python-heap/python-heap/
作者
Yiwei Zhang
发布于
2022年5月15日
许可协议