Python标准库系列-heapq

Python 3提供了一系列标准库，所提供的组件设计范围十分广泛。这个标准库包含了多个内置模块（以C编写），Python可以依靠这些标准库提供许多系统级功能，例如文件I/O，此外还有大量以Pyhon编写的模块，提供了许多日常编程中许多问题的标准解决方案。具体的列表可以点击Python标准库了解。

今天提供的就是heapq这个标准库的使用说明

heapq

heapq所提供的就是堆队列算法，也称为 优先队列算法， 二叉堆。

二叉堆

堆的本质是一种完全二叉树，又分为：

• 最小堆（小根堆）：树中每个非叶字节点都不大于其左右孩子节点的值，也就是根节点最小的堆

• 最大堆（大根堆）：树中每个非叶子节点都不小于其左右孩子节点的值，也就是根节点最大的堆

二叉堆分析

在实际使用过程中，我们用数组来存储二叉堆。从a[1]开始存储，对于下标为k的节点a[k]说，其左孩子的下标为2 * k，其右孩子的下标为2 * k + 1。且不管k是奇数还是偶数，其父节点下标都为k / 2

向上调整（添加）

假如我们向一个堆中插入一个元素，要使其仍然保持堆的结构。应该怎么办呢？

​可以把想要添加的元素放在数组的最后，也就是完全二叉树的最后一个节点的后面，然后进行向上调整（heapinsert）。向上调整总是把欲调整节点与父亲节点比较，如果权值比父亲节点大，那么就交换其与父亲节点，反复比较，直到到达堆顶或父亲节点的值较大

时间复杂度为𝑂(𝑙𝑜𝑔𝑛)

向下调整（删除堆顶）

​假如我们要删除一个堆中的堆顶元素，要使其仍然保持堆的结构。应该怎么办呢？

​移除堆顶元素后，将最后一个元素移动到堆顶，然后对这个元素进行向下调整（heapify），向下调整总是把欲调整节点K与其左右孩子节点比较，如果孩子中存在权值比当前节点K大的，那么就将其中权值最大的那个孩子节点与节点K反复比较，直到到节点K为叶子节点或节点K的值比孩子节点都大为止。

时间复杂度也是𝑂(𝑙𝑜𝑔𝑛)

适用范围

因为堆的根节点特性，特别适合需要追踪最大值/最小值的程序，比如寻找第K大元素等

heapq标准库

要创建一个堆，可以使用list来初始化为[]，或者通过heapify()，来把一个list转换为堆。heapq会设置为最小堆。

heapq定义了以下函数

• heapq.headpush(heap, item)
  将 item 的值加入到heap中，保持堆的不变性

• heapq.heappop(heap)
  弹出并返回 heap 的最小值，保持堆的不变性

• 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还提供三个基于堆的通用功能函数

• heapq.merge(*iterables, key=None, reverse=False)
  将多个已排序的输入合并为一个已排序的输出（例如，合并来自多个日志文件的带时间戳的条目）。 返回已排序值的 iterator。
  类似于 sorted(itertools.chain(*iterables)) 但返回一个可迭代对象，不会一次性地将数据全部放入内存，并假定每个输入流都是已排序的（从小到大）。

• 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]。

后两个函数在 n 值较小时性能最好。 对于更大的值，使用 sorted() 函数会更有效率。 此外，当 n==1 时，使用内置的 min() 和 max() 函数会更有效率。 如果需要重复使用这些函数，请考虑将可迭代对象转为真正的堆。

示例

Python 中 heapq 模块是小顶堆。实现 大顶堆 方法： 小顶堆的插入和弹出操作均将元素 取反 即可。

from heapq import *

class MedianFinder:
    def __init__(self):
        self.A = [] # 小顶堆，保存较大的一半
        self.B = [] # 大顶堆，保存较小的一半

    def addNum(self, num: int) -> None:
        if len(self.A) != len(self.B):
            heappush(self.B, -heappushpop(self.A, num))
        else:
            heappush(self.A, -heappushpop(self.B, -num))

    def findMedian(self) -> float:
        return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0