Python 堆

本文记录 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) 将列表转化为堆

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]。

参考资料

• 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/