heapq实现了一个适合与Python的列表一起使用的最小堆排序算法。
满二叉树
树中除了叶子节点,每个节点都有两个子节点
完全二叉树
在满足满二叉树的性质后,最后一层的叶子节点均需在最左边
堆
堆是一种数据结构,它是一颗完全二叉树。最小堆则是在堆的基础增加了新的规则,它的根结点的值是最小的,而且它的任意结点的父结点的值都小于或者等于其左右结点的值。因为二进制堆可以使用有组织的列表或数组来表示,所以元素N的子元素位于位置2 * N + 1和2 * N + 2。这种布局使重新安排堆成为可能,因此在添加或删除项时不需要重新分配那么多内存
区分堆(heap)与栈(stack):堆与二叉树有关,像一堆金字塔型泥沙;而栈像一个直立垃圾桶,一列下来。
最大堆
最大堆确保父堆大于或等于它的两个子堆。
最小堆
建堆:
最小堆要求父堆小于或等于其子堆。Python的heapq模块实现了一个最小堆。
要创建一个堆,可以使用list来初始化为 []
,或者你可以通过一个函数 heapify()
,来把一个list转换成堆。
定义了以下函数:heapq.
heappush
(heap, item)
将 item 的值加入 heap 中,保持堆的不变性。
弹出并返回 heap 的最小的元素,保持堆的不变性。如果堆为空,抛出 IndexError
。使用 heap[0]
,可以只访问最小的元素而不弹出它。
将 item 放入堆中,然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush()
再调用 heappop()
运行起来更有效率。
将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]
。