欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Python之heapq模块

程序员文章站 2024-03-15 21:34:48
...

1 heapq

该模块提供堆队列算法实现,即队列优先算法。堆是二项树,树中的父节点的值小于等于其子节点值,该算法使用数组heap[k]<=heap[2k+1]heap[k]<=heap[2*k+1]heap[k]<=heap[2k+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