优先队列不支持删除任意元素或修改优先级时怎么办？

简化版

普通二叉堆只能高效删除堆顶，不擅长删除任意元素或原地修改优先级。常见做法是“懒删除”：新优先级重新入堆，旧记录留在堆里，弹出时检查是否过期；需要严格删除时再维护元素到堆下标的索引表。

详细版

标准库优先队列通常支持：

插入：O(log n)
查看堆顶：O(1)
删除堆顶：O(log n)

但它通常不支持高效删除任意元素、修改某个元素的优先级。解决方式有两类：

懒删除：不删除旧记录，插入新记录；弹出堆顶时发现旧记录就跳过。
索引堆：额外维护 id -> index，定位元素后上浮或下沉，支持 decreaseKey/increaseKey/delete。

Dijkstra 常用懒删除：同一个节点可能多次入堆，弹出时若 d > dist[u]，说明这条记录已过期，跳过即可。

while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int d = cur[0], u = cur[1];
    if (d > dist[u]) continue; // 旧记录
    // 用 u 松弛邻居
}

完整版教学

一、普通堆为什么不擅长删除任意元素

二叉堆的优势来自数组存储和局部堆序。删除堆顶很快，因为堆顶下标固定为 0；但如果要删除某个任意元素，首先要在数组里找到它的位置。标准堆没有 元素 -> 下标 的索引，只能线性扫描，定位就要 O(n)。

heap array: [1, 3, 2, 8, 5, 7]
想删除元素 5：
  如果不知道 5 在哪里，只能扫描数组
  找到后再和末尾交换、上浮或下沉

所以问题不在“堆不能调整”，而在“找不到要调整的那个元素”。索引堆就是给堆额外配一张地图，懒删除则干脆不找旧元素。

二、懒删除的核心思想

懒删除不急着把旧记录从堆中移除，而是让它自然浮到堆顶时再判断是否有效。因为只有堆顶会被真正消费，非堆顶的旧记录即使留着，也暂时不影响答案。这个思想在 Dijkstra、滑动窗口中位数、定时任务取消中都很常见。

节点 A 原距离 10 入堆
后来发现 A 新距离 6，再入堆

堆里同时有：
  (6, A)   新记录
  (10, A)  旧记录

弹出 (6,A)：有效，处理
弹出 (10,A)：发现 10 > dist[A]=6，跳过

懒删除用空间换实现简单。旧记录会增加堆大小，但每条旧记录最终最多被弹出并跳过一次，所以总复杂度通常仍可接受。

三、用版本号或当前值判断过期

判断过期有多种方式。Dijkstra 用 d > dist[u]，因为 dist[u] 保存当前最优距离；定时任务可以用任务版本号；滑动窗口可以用哈希表记录待删除次数。核心都是“堆顶记录”和“外部真实状态”做一次校验。

class Entry {
    int id;
    int priority;
    int version;
}

if (entry.version != currentVersion[entry.id]) {
    continue; // 旧版本，跳过
}

版本号方式适合优先级可能升高也可能降低的场景，因为不能只用大小关系判断。外部状态是懒删除的事实来源，堆只是候选记录容器。

四、索引堆什么时候更合适

如果题目或系统要求“删除任意元素必须立刻生效”，或者堆中旧记录太多无法接受，就可以实现索引堆。索引堆维护 pos[id] = index，修改优先级时先定位数组位置，再根据新旧优先级决定上浮或下沉。

方案	任意删除	修改优先级	实现复杂度	典型场景
标准优先队列	慢	慢	低	Top K、普通调度
懒删除	逻辑删除	重新入堆	中	Dijkstra、取消任务
索引堆	`O(log n)`	`O(log n)`	高	频繁改优先级

索引堆更强，但代码更容易出错：每次交换堆数组元素时，都必须同步更新 pos。面试中如果不是明确要求，懒删除通常更稳。

五、复杂度怎么分析才准确

懒删除的单次堆操作仍是 O(log H)，H 是包含旧记录的堆大小。虽然堆中可能有过期记录，但每条记录只会入堆一次、出堆一次。以 Dijkstra 为例，每次松弛成功会入堆一次，最多 O(E) 条记录，因此总复杂度常写 O(E log E)，也可简化为 O(E log V) 量级表达。

真实有效记录：V 个左右
历史过期记录：最多来自松弛成功次数
每条记录：
  入堆一次
  弹出一次
  有效则处理，无效则跳过

如果业务中一个元素被反复修改百万次且很少弹出，懒删除会造成堆膨胀，这时索引堆或可删除堆结构更合适。复杂度分析要结合“修改频率”和“弹出频率”。

六、常见误区与追问

记忆钩子：懒删除不是忘记删除，而是把删除推迟到“它冒到堆顶、即将影响答案”的那一刻。

误区：优先队列可以高效删除任意元素。 标准二叉堆没有元素下标索引，定位通常要 O(n)。
误区：懒删除会导致答案错误。 只要弹出时用真实状态校验，旧记录不会被消费。
误区：重新入堆等于内存无限增长。 旧记录确实增加空间，但会在后续弹出时被清理；是否可接受要看场景。
追问：Dijkstra 为什么可以多次把同一节点入堆？ 新距离入堆，旧距离弹出时通过 d > dist[u] 跳过。
追问：什么时候必须用索引堆？ 需要频繁、立即地删除任意元素或修改优先级时。
追问：版本号比大小判断有什么优势？ 它能处理优先级升高、降低、任务取消等更通用的过期判断。

七、加强记忆

优先队列的短板是“只认识堆顶，不认识任意元素在哪里”。懒删除的办法是不和堆数组硬碰硬：更新时插入新记录，旧记录留着；弹出时拿堆顶和外部真实状态校验，过期就跳过。索引堆则是更强但更复杂的方案，通过 id -> index 定位元素并调整堆。记忆时抓住取舍：普通堆简单，懒删除工程常用，索引堆适合高频改优先级。

简化版

详细版