算法实现中经常需要构造和处理一些特殊的数据结构，Python 标准库中有一些模块可以帮到我们。
collections 实用容器
collections模块实现了一些特定目标的容器，以提供 Python 标准内建容器 dict , list , set , 和 tuple 的替代选择。
deque
在 Python 中从list对象的头部删除元素，时间复杂度是 O(n)。deque类型是一个双向队列，类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)。
q = deque([1, 2, 3, 4])
q.append(5)
q.appendleft(0)
assert q == deque([0, 1, 2, 3, 4, 5])
assert q.pop() == 5
assert q.popleft() == 0
assert len(q) == 4在广度优先搜索的算法实现中，deque类型是一个不错的选择。
defaultdict
defaultdict是字典的子类，提供了一个工厂函数，为字典查询提供一个默认值
counter = defaultdict(int)
for ch in "aaabbbccc":
counter[ch] = 1
assert counter == {"a": 3, "b": 3, "c": 3}Counter
Counter也是字典的子类，提供了可哈希对象的计数功能。使用Counter类型可以使用一条语句替代上述的字母计数的实现。
assert Counter("aaabbbccc") == {"a": 3, "b": 3, "c": 3}heapq 二叉堆算法
heapq模块提供了堆队列算法的实现，也称为优先队列算法。
堆是一个二叉树，它的每个父节点的值都只会小于或等于所有孩子节点（的值）。 它使用了数组来实现：从零开始计数，对于所有的 k ，都有 heap[k] <= heap[2k 1] 和 heap[k] <= heap[2k 2]。 为了便于比较，不存在的元素被认为是无限大。 堆最有趣的特性在于最小的元素总是在根结点：heap[0]。 这个 API 与教材的堆算法实现有所不同，具体区别有两方面：（a）我们使用了从零开始的索引。这使得节点和其孩子节点索引之间的关系不太直观但更加适合，因为 Python 使用从零开始的索引。 （b）我们的 pop 方法返回最小的项而不是最大的项（这在教材中称为“最小堆”；而“最大堆”在教材中更为常见，因为它更适用于原地排序）。 基于这两方面，把堆看作原生的 Python list 也没什么奇怪的： heap[0] 表示最小的元素，同时 heap.sort() 维护了堆的不变性！ 要创建一个堆，可以使用 list 来初始化为 [] ，或者你可以通过一个函数 heapify() ，来把一个 list 转换成堆。
一个简单的堆排序的示例如下：
代码语言：javascript复制def heap_sort(nums):
heapq.heapify(nums)
return [heapq.heappop(nums) for _ in range(len(nums))]
assert heap_sort([3, 1, 2]) == [1, 2, 3]当然在现实的算法实现中，一般不会去完整的实现一个堆排序。heapq模块主要应用在一些需要部分排序的算法实现中，例如 TopK 问题。
def top_k(arr: list[int], k: int) -> list[int]:
heapq.heapify(arr)
return heapq.nlargest(k, arr)
assert top_k([3, 1, 2], 2) == [3, 2]bisect 二分查找
bisect模块提供了数组二分查找算法。
值得一提的是bisect模块的函数一般是返回新的插入位置，要检查一个元素是否在排序列表中，需要一点额外的判断。
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def find_lt(a, x):
'Find rightmost value less than x'
i = bisect_left(a, x)
if i:
return a[i-1]
raise ValueError
def find_le(a, x):
'Find rightmost value less than or equal to x'
i = bisect_right(a, x)
if i:
return a[i-1]
raise ValueError
def find_gt(a, x):
'Find leftmost value greater than x'
i = bisect_right(a, x)
if i != len(a):
return a[i]
raise ValueError
def find_ge(a, x):
'Find leftmost item greater than or equal to x'
i = bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueErrorPython 官方文档给了一个体现bisect模块实用性的非常合适的例子（代码稍有调整）。
代码语言：javascript复制函数 bisect() 还可以用于数字表查询。这个例子是使用 bisect() 从一个给定的考试成绩集合里，通过一个有序数字表，查出其对应的字母等级：90 分及以上是 ‘A’，80 到 89 是 ‘B’，以此类推
def grade(score, breakpoints=[60, 70, 80, 90], grades="FDCBA"):
i = bisect.bisect(breakpoints, score)
return grades[i]
grades = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
assert grades == ["F", "A", "C", "C", "B", "A", "A"]
bisect模块还提供了一个insort函数用于向一个有序列表中插入元素。不过即使确定插入位置的时间复杂度是 O(logN)，但向列表中插入元素的时间复杂度为 O(n)，实用性相当有限。
好在 LeetCode 的 Python 环境安装并导入了sortedcontainers模块，提供了SortedList，SortedDict等实用类型。
graphlib 拓扑排序
graphlib是 Python3.9 引入的新模块，提供了拓扑排序的功能。
>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')总结
这些模块可以帮助构造想要的数据结构，实现具体的算法。
