python 的heapq和itertools
heapq
官方介绍文档
这个模块提供了对堆队列算法/优先队列算法的实现。此处的堆指的是大顶堆/小顶堆。
在python中,使用了数组来实现大顶堆和小顶堆, 假设这个堆为heap:
- 对于小顶堆来说,从0开始计数,所有的第k个元素,都有
heap[k] <= heap[2*k+1]
和heap[k] <= heap[2*k+2]
, 即根节点小于子节点 - 对于大顶堆来说则正好相反:
heap[k] >= heap[2*k+1]
和heap[k] >= heap[2*k+2]
在heapq
中,这里的堆指的是小顶堆,最小元素总是在根节点heap[0]。
heapq这个API同教材上的堆算法是不同的,主要在两个方面:
- 使用0作为起始索引,这样会使得父节点和子节点之间的索引关系变得不那么明显,但是在python中这是很合适的,因为
python
的list
使用0
作为起始索引。 pop
方法返回的是最小元素而不是最大元素,
heapq方法一览
heap.heappush(heap, item)
# 往一个堆里面push一个元素
heap.heappop(heap)
# 将堆里面的最小元素返回,如果heap是空的话,会引起IndexError
heap.heappushpop(heap, item)
# 先往堆里面推入一个元素,然后将堆中的最小元素pop出来并返回
# 这个方法比先调用和heappush()然后调用heappop()要高效的多
heapq.heapify(x:list)
# 将列表x在 线性时间内 原地转化为堆结构
heapq.heapreplace(heap, item)
# 首先,将堆中的最小元素pop出来,返回
# 然后,将新的item 推入到堆里面,堆的长度不变
# 相当于先调用heappop,再调用heappush, 与heappushpop刚好相反,一般情况下结果是一样的
# 如果想要返回的元素比参数item小,可以用heapq.heappushpop()
heapq.merge(*iterables, key=None, reverse=False)
# 合并两个有序的iter可迭代对象(列表/集合/...)
# 返回的也是一个可迭代对象
heapq.nlargest(n, iterable, key=None)
# 返回可迭代对象iterable里面的前n个最大值
# 返回的是一个列表
heapq.nsmallest(n, iterable, key=None)
# 返回可迭代对象iterable里面的前n个最小值
# 返回的是一个列表
itertools
itertools 是为高效循环而创建的迭代器函数
一般情况下主要使用到的方法有三个:
- permutations(iterable) --> 创建一个全排列的列表并返回
- combinations(iterable, count) --> 组合工具:从iterable可迭代对象里面选择count个元素,返回所有的组合方式
- product(iterableA, iterableB) --> 迪卡尔积