# 动态集合取最值优化：Heap


<!--post-->

## 问题模式

维护一个动态字典：

```python
state = {
    item: value
}
```

循环执行：

1. 获取 value 最大/最小的 item
2. 修改 state

朴素实现：

```python
max(state, key=state.get)
```

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

------

## 优化：Heap + HashMap

维护两个结构：

- HashMap：保存真实状态
- Heap：快速获取候选最值

复杂度：

| 操作      | 复杂度         |
| --------- | -------------- |
| heap push | O(logN)        |
| heap pop  | O(logN)        |
| 查找最值  | O(1)（取堆顶） |

------

## Lazy Deletion（惰性删除）

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

因此：

更新状态时：

1. 修改 HashMap
2. 新值重新 push 到 heap
3. 弹出时检查是否过期

示例：

```python
state["a"] = 100

heap:
(-100, "a")
```

更新后：

```python
state["a"] = 20

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

取值：

```python
while heap:
    value, item = heappop(heap)

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

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


---

> 作者: [fupcode](https://github.com/fupcode)  
> URL: https://fupcode.com/blog/posts/algorithm/perf-dict-with-heap/