python堆队列算法：heapq

堆队列算法:heapq

• import headq
• 要创建堆，请使用已初始化的列表[]

方法

• heapq.heappush(<heap>,<item>) 将值项推送到堆上，保持堆不变
• heapq.heappop(<heap>) 弹出并返回堆中的最小项，保持堆不变，如果堆为空，IndexError则引发
• heapq.heappushpop(<heap>,<item>) 在堆上推送项目，然后弹出并返回堆中的最小项目
• heapq.heapify(<list) 在线性时间内将列表转换为堆
• heapq.heapreplace(<heap>,<item>) 弹出并返回堆中的最小项，并同时推送新项，堆大小不会改变，如果堆为空，IndexError则引发,注意：返回的值可能大于添加的项目
• heapq.merge（<*iterables>，key = None，reverse = False ） 将多个已排序的输入合并为单个排序的输出
• heapq.nlargest（n，iterable，key = None ） 返回一个列表，其中包含iterable定义的数据集中的n个最大元素
• heapq.nsmallest（n，iterable，key = None ） 返回一个列表，其中包含iterable定义的数据集中的n个最小元素

Demo

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• 堆元素可以是元组

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')