Python标准库模块之heapq

Python014

Python标准库模块之heapq,第1张

该模块提供了堆排序算法的实现。堆是二叉树，最大堆中父节点大于或等于两个子节点，最小堆父节点小于或等于两个子节点。

heapq有两种方式创建堆， 一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中，另外一种就是使用heap.heapify(list)转换列表成为堆结构

heapq 模块还有一个 heapq.merge(*iterables) 方法，用于合并多个排序后的序列成一个排序后的序列， 返回排序后的值的迭代器。

类似于 sorted(itertools.chain(*iterables)) ，但返回的是可迭代的。

堆创建好后，可以通过`heapq.heappop() 函数弹出堆中最小值。

如果需要删除堆中最小元素并加入一个元素，可以使用 heapq.heaprepalce() 函数

如果需要获取堆中最大或最小的范围值，则可以使用 heapq.nlargest() 或 heapq.nsmallest() 函数

这两个函数还接受一个key参数，用于dict或其他数据结构类型使用

实现heap堆排序算法

该算法和 sorted(iterable) 类似，但是它是不稳定的。

堆的值可以是元组类型，可以实现对带权值的元素进行排序。

Python3标准库文档

Python堆排序

堆特征：堆列表位置i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i 和 2 * i + 1处的元素）

heapify(list) 让列表具有堆特征

heappush(heap, item) 将值压入堆中

heappop(heap)从堆中弹出最小的元素

heapreplace(heap, item) 弹出最小的元素，并将值压入堆中

nlargest(n, iterable, key=None) 返回堆中n个最大的元素

nsmallest(n, iterable, key=None)返回堆中n个最小的元素

heappushpop(heap, item) 将item压入堆中然后弹出最小的元素

merge(*iterables, key=None, reverse=False) 将有序序列进行合并排序，返回生成器序列