Python之heapq模块

1 heapq

该模块提供堆队列算法实现，即队列优先算法。堆是二项树，树中的父节点的值小于等于其子节点值，该算法使用数组$heap[k]&lt;=heap[2*k+1]$heap[k]<=heap[2∗k+1]和$heap[k]&lt;=heap[2*k+2]$heap[k]<=heap[2∗k+2]表示所有的k,从0开始计数，为了进行比较，不存在的元素记为无穷大，堆的一个有趣的属性是她的最小元素总是根元素$heap[0]$heap[0]。

2 方法

2.1 heappush(heap, item)

功能：将item的值推送到heap中，保持堆不变。

• Demo

import heapq
h = [1, 4, 56, 2, 5]
result = []
for value in h:
    heapq.heappush(result, value)
print("result form heap push: {}".format(result))

• Result

result form heap push: [1, 4, 56, 2, 5]

2.2 heappop(heap)

功能：从heap中取值并返回最小的值，保持堆不变，若heap为空，报IndexError警告，使用$heap[0]$heap[0]即可获取最小的值，而不用pop。

• Demo

import heapq
h = [1, 4, 56, 2, 5]
result = []
for value in h:
    heapq.heappush(result, value)
print("result form heap push: {}".format(result))
pop_result = [heapq.heappop(result) for i in range(len(result))]
print("result from pop: {}".format(pop_result))

• Result

result form heap push: [1, 2, 56, 4, 5]
result from pop: [1, 2, 4, 5, 56]

2.3 heappushpop(heap, item)

功能：将item推送到heap，然后取出，并返回最小的值。

• Demo

import heapq
h = [1, 4, 56, 2, 5, 6]
# 取出h中的第一个值
# 保持heap尺寸不变，将3推进heap
combine_result = heapq.heappushpop(h, 3) 
print("result form heap push: {}".format(combine_result))
print("new heap: {}".format(h))

• Result

result form heap push: 1
new heap: [4, 2, 56, 3, 5, 6]

2.4 heapify(x)

功能：将列表x以线性时间方式转为堆。

• Demo

import heapq
a = [1, 4, 5, 0]
heapq.heapify(a)
print("heapify result: {}".format(a))

• Result

heapify result: [0, 1, 5, 4]

2.5 heapreplace(heap, item)

功能：从heap中取出并返回第一个值，将item推入heap，保持堆尺寸，若heap为空，报IndexError警告。

• Demo

import heapq
a = [12, 33, 5, 10]
c = heapq.heapreplace(a, 2)
print("heap replace result: {}".format(c))
print("result: {}".format(a))

• Result

heap replace result: 12
result: [2, 33, 5, 10]

2.6 merge(*iterables)

功能：多个输入合并为单个输出，返回排序的结果。

• Demo

import heapq
a = [1, 33, 5, 10]
b = [3, 6, 7, 0, -1]
c = list(heapq.merge(b, a))
print("merge result: {}".format(c))

• Result

merge result: [1, 3, 6, 7, 0, -1, 33, 5, 10]

2.7 nlargest(n, iterable[,key])

功能：从可遍历的数据集中返回n个最大的元素组成的列表。

• Demo

import heapq
a = [1, 3, 4, 5, 6]
larger = heapq.nlargest(2, a)
print("largest two number: {}".format(larger))

• Result

largest two number: [6, 5]

2.8 nsmallest(n, iterable[,key])

功能：从可遍历的数据集中返回n个最小的元素组成的列表。

• Demo

import heapq
a = [1, 3, 4, 5, 6]
smaller = heapq.nsmallest(2, a)
print("smallest two number: {}".format(smaller))

• Result

smallest two number: [1, 3]

---

[参考文献]
[1]https://docs.python.org/2/library/heapq.html

---