python3中的heapq 堆

heapq实现了一个适合与Python的列表一起使用的最小堆排序算法。

满二叉树

树中除了叶子节点，每个节点都有两个子节点

完全二叉树

在满足满二叉树的性质后，最后一层的叶子节点均需在最左边

堆

堆是一种数据结构，它是一颗完全二叉树。最小堆则是在堆的基础增加了新的规则，它的根结点的值是最小的，而且它的任意结点的父结点的值都小于或者等于其左右结点的值。因为二进制堆可以使用有组织的列表或数组来表示，所以元素N的子元素位于位置2 * N + 1和2 * N + 2。这种布局使重新安排堆成为可能，因此在添加或删除项时不需要重新分配那么多内存
区分堆(heap)与栈(stack)：堆与二叉树有关，像一堆金字塔型泥沙；而栈像一个直立垃圾桶，一列下来。

最大堆

最大堆确保父堆大于或等于它的两个子堆。

最小堆

建堆：

 heapify()

最小堆要求父堆小于或等于其子堆。Python的heapq模块实现了一个最小堆。

要创建一个堆，可以使用list来初始化为 [] ，或者你可以通过一个函数 heapify() ，来把一个list转换成堆。

定义了以下函数：heapq.heappush(heap, item)

将 item 的值加入 heap 中，保持堆的不变性。

heapq.heappop(heap)

弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出 IndexError 。使用 heap[0] ，可以只访问最小的元素而不弹出它。

heapq.heappushpop(heap, item)

将 item 放入堆中，然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。

heapq.heapify(x)

将list x 转换成堆，原地，线性时间内。heapq.heapreplace(heap, item)

弹出并返回 heap 中最小的一项，同时推入新的 item。 堆的大小不变。 如果堆为空则引发 IndexError。

这个单步骤操作比 heappop() 加 heappush() 更高效，并且在使用固定大小的堆时更为适宜。 pop/push 组合总是会从堆中返回一个元素并将其替换为 item。

返回的值可能会比添加的 item 更大。 如果不希望如此，可考虑改用 heappushpop()。 它的 push/pop 组合会返回两个值中较小的一个，将较大的值留在堆中。

heapq.nlargest(n, iterable, key=None)

从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key, reverse=True)[:n]。

heapq.nsmallest(n, iterable, key=None)

从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。 如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。 等价于: sorted(iterable, key=key)[:n]。