python heapq module

简介

Python提供的关于堆的操作模块。

Python 提供的是基于小顶堆的操作，因此 Python 可以对 list 中的元素进行小顶堆排列，这样程序每次获取堆中元素时，总会取得堆中最小的元素。

有关堆的介绍：传送门

用法

heapq 模块包含的方法

1
2
3

>>> import heapq
>>> heapq.__all__
['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']

用法

heap = []            # creates an empty heap
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
item = heap[0]       # smallest item on the heap without popping it
heapify(x)           # transforms list into a heap, in-place, in linear time
item = heapreplace(heap, item) # pops and returns smallest item, and adds new item; the heap size is unchanged

示例

创建一个堆

>>> import heapq

# 创建一个堆
# 方法一: 创建一个空的列表，然后向里面添加元素
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heap
[5]

# 方法二：将非空列表堆化
>>> heap = [7, 1, 2, 8, 6, 9, 10]
>>> heapq.heapify(heap)
>>> heap[0]
1

方法使用

heapq.heapify(x)

将list x 转换成堆。

>>> import heapq
>>> heap = [7, 1, 2, 8, 6, 9, 10]

>>> heapq.heapify(heap)

heapq.heappush(heap, item)
将item的值加入 heap 中，保持堆的不变性。
1
2
3
>>> heapq.heappush(heap, -5)
>>> heap
[-5, 1, 2, 6, 7, 9, 10, 8]
heapq.heappop(heap)
弹出并返回 heap 的最小的元素，保持堆的不变性。

如果堆为空，抛出 IndexError 。

使用 heap[0] ，可以只访问最小的元素而不弹出它。
1
2
3
4
>>> heapq.heappop(heap)
-5
>>> heap
[1, 5, 2, 6, 7, 9, 10, 8]
heapq.heappushpop(heap, item)
将 item 放入堆中，然后弹出并返回 heap 的最小元素。

该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。
1
2
3
4
>>> heapq.heappushpop(heap, 3)
1
>>> heap
[2, 5, 3, 6, 7, 9, 10, 8]
heapq.heapreplace(heap, item)
弹出并从堆中返回最小的项，然后将 item 放入堆中。如果堆是空的，则引发 IndexError。
该组合操作先调用 heappop() 在调用 heappush() 更有效。

注：返回的值可能大于添加的项。如果不希望这样，可以用 heapq.heappushpop()。
1
2
3
4
>>> heapq.heapreplace(heap, -2)
2
>>> heap
[-2, 5, 3, 6, 7, 9, 10, 8]

heapq.merge(*iterables, key=None, reverse=False)

将多个有序的输入（从小到大排序）合并到一个有序的输出中。返回已排序值的迭代器。

key：比较函数，该参数用于从每个输入元素中提取一个比较键。默认值是None(直接比较元素)。
reverse：布尔值。如果设置为True，要实现逆序排列，所有的iterables都必须从大到小排序

# 从小到大排序
>>> a = [1, 3, 5]       
>>> b = [2, 4, 6]      
>>> list(heapq.merge(a, b))      
[1, 2, 3, 4, 5, 6]

# 从大到下排序
>>> a = [5, 3, 1] 
>>> b = [6, 4, 2]
>>> list(heapq.merge(a, b, reverse=True))
[6, 5, 4, 3, 2, 1]

heapq.nlargest(n, iterable, key=None)
从iterable定义的数据集中返回一个包含n个最大元素的列表。

key: 比较函数，该参数用于从iterable中的每个元素中提取一个比较键

等价于: sordered (iterable, key=key, reverse=True)[:n]
1
2
3
4
5
6
7
8
>>> import heapq

>>> heap = [7, 1, 2, 8, 6, 9, 10]
>>> heapq.nlargest(2, heap)
[10, 9]
>>> heapq.nsmallest(2, heap)

[1, 2]
heapq.nsmallest(n, iterable, key=None)
从iterable定义的数据集中返回一个包含n个最小元素的列表。

key: 比较函数，该参数用于从iterable中的每个元素中提取一个比较键

等价于: sordered (iterable, key=key)[:n]
1
2
3
4
5
>>> import heapq

>>> heap = [7, 1, 2, 8, 6, 9, 10]
>>> heapq.nsmallest(2, heap)
[1, 2]

简介

用法

heapq.heapify(x)

heapq.heappush(heap, item)

heapq.heappop(heap)

heapq.heappushpop(heap, item)

heapq.heapreplace(heap, item)

heapq.merge(*iterables, key=None, reverse=False)

heapq.nlargest(n, iterable, key=None)

heapq.nsmallest(n, iterable, key=None)