优先队列——延迟删除

延迟删除是一种结合优先队列（堆）与懒标记的技巧，用于解决堆不支持直接删除任意元素的问题。

为什么需要延迟删除？

std::priority_queue只允许访问堆顶，无法直接移除堆中间的元素。但在许多算法（如天际线、Dijkstra 中的边松弛）中，我们可能需要将某个已入堆的元素标记为“无效”，待它自然上升到堆顶时再丢弃。

实现原理

1. 额外维护一个“待删除”计数器（哈希表）：unordered_map<ValueType, int> toRemove。

2. 逻辑删除：当需要删除某个值v时，不直接在堆中操作，而是toRemove[v]++。

3. 物理清理：每次取堆顶前，检查当前堆顶是否在toRemove中有待删除计数。若有，则弹出堆顶并减少计数，重复该过程直到堆顶是真正活跃的元素。

通用模板

cpp

priority_queue<T> pq; // 最大堆 unordered_map<T, int> pending; // 待删除计数 void insert(T val) { pq.push(val); } void lazy_erase(T val) { pending[val]++; } T top() { while (!pq.empty() && pending[pq.top()] > 0) { pending[pq.top()]--; pq.pop(); } return pq.top(); // 调用前需确保非空 }

注意事项

• 重复值处理：必须用计数器（int），不能用简单的bool，因为可能有多个相同值的元素需要分别删除。

• 性能：每个元素至多入堆、出堆一次，哈希表操作 O(1) 均摊，整体复杂度不受影响。

• 适用场景：任何需要动态删除堆中非顶部元素的场合，如天际线问题、Dijkstra 松弛优化（改用pair<dist,node>且不修改而是插入新距离，旧距离被懒惰丢弃）。

天际线问题中的实际代码（片段）

cpp

priority_queue<int> pq; // 最大堆，存高度 unordered_map<int, int> toRemove; pq.push(0); for (事件 e : events) { if (e.isLeft) pq.push(e.height); else toRemove[e.height]++; // 清理堆顶已标记删除的高度 while (!pq.empty() && toRemove[pq.top()] > 0) { toRemove[pq.top()]--; pq.pop(); } int curHeight = pq.top(); // 处理高度变化... }

总之，延迟删除是堆结构的一种经典补丁，以较小的额外空间和时间代价，模拟了“可删除优先队列”的行为。