heapq 模块提供堆算法,官方文档写的很好,摘抄下来(对格式和段落进行了整理):
NAME:
This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.
heapq 实现了 heap queue 算法(也叫做 priority queue algorithm)
DESCRIPTION
Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].
bisect
bisect
一个二分法的库,最大的价值是提供一个二分法算法示例
import bisect
a=[1,2,3,3,5,6,7]
# 找到可以把 x 插入 a 的 index,使得 a 仍然能保持顺序
# 其中,a 是 升序的 list,x 是 value
bisect.bisect_left(a=a,x=3,lo=0,hi=len(a)) # 遇到 x in a 的情况,输出最左边的可插入的index
bisect.bisect_right(a=a,x=3) # 遇到 x in a 的情况,输出最右边可插入的 index (注意,a中最右边的index)
bisect.bisect(a=a,x=3) # 完全等价于 bisect.bisect_right
bisect.insort_left(a=a,x=4,lo=0,hi=len(a))
# equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x)
# 记住,虽然 binary search 是 O(lg n)的,但 insert 是 O(n) 的
bisect.insort_right(a=a,x=4,lo=0,hi=len(a))
# a.insert(bisect.bisect_right(a, x, lo, hi), x)
应用举例
想把百分制的考试成绩,转化为’ABCDF’这种标志
breakpoints = [60, 70, 80, 90] # 隔断区间
grades = 'FDCBA' # 标志
scores = [33, 99, 77, 70, 89, 90, 100] # 同学们的分数
[grades[bisect.bisect_left(a=breakpoints,x=i)] for i in scores]
参考文献
https://docs.python.org/3/