https://www.jianshu.com/p/801318c77ab5
python标准库模块heapq
该模块提供了堆排序算法的实现。堆是二叉树,最大堆中父节点大于或等于两个子节点,最小堆父节点小于或等于两个子节点。
创建堆
heapq有两种方式创建堆, 一种是使用一个空列表,然后使用heapq.heappush()函数把值加入堆中,另外一种就是使用heap.heapify(list)转换列表成为堆结构
heapq 模块还有一个heapq.merge(*iterables)方法,用于合并多个排序后的序列成一个排序后的序列, 返回排序后的值的迭代器。
类似于sorted(itertools.chain(*iterables)),但返回的是可迭代的。
访问堆内容
堆创建好后,可以通过`heapq.heappop() 函数弹出堆中最小值。
如果需要删除堆中最小元素并加入一个元素,可以使用heapq.heaprepalce() 函数
获取堆最大或最小值
如果需要获取堆中最大或最小的范围值,则可以使用heapq.nlargest() 或heapq.nsmallest() 函数
这两个函数还接受一个key参数,用于dict或其他数据结构类型使用
heapq应用
实现heap堆排序算法
该算法和sorted(iterable)类似,但它是不稳定的
堆的值可以是元组类型,可以实现对带权值的元素进行排序。
网友评论