动态集合取最值优化：Heap

2026-08-06 2026-10-15 约 300 字预计阅读 1 分钟

问题模式

维护一个动态字典：

1
2
3
state = {
    item: value
}

循环执行：

朴素实现：

1
max(state, key=state.get)

每次扫描复杂度为 $O(N)$

维护两个结构：

复杂度：

Heap 不支持高效修改已有元素。

因此：

更新状态时：

示例：

1
2
3
4
state["a"] = 100

heap:
(-100, "a")

更新后：

1
2
3
4
5
state["a"] = 20

heap:
(-100, "a")  # stale
(-20, "a")   # valid

取值：

1
2
3
4
5
6
while heap:
    value, item = heappop(heap)

    if value == current_state[item]:
        use(item)
        break

注意

Python 中使用 heapq 库时，如果要支持自定义类排序，需要实现类的 __lt__ 和 __eq__ 魔术方法。