题干与适用场景
请实现一个优先队列，支持 add(task, priority)、update(task, priority)、remove(task) 和 pop()。相同优先级必须按加入顺序返回；删除和更新的均摊复杂度应为 O(log n)，并说明如何处理堆中的失效条目。
这道题考察可变优先队列的正确性，而不是只会调用一个 heap API。Python heapq 文档指出，优先队列需要处理稳定排序、不可比较任务、优先级变化和待删除元素；常见做法是用计数器解决平局，用字典定位条目，再用惰性删除维护堆不变量。
面试官考察点
第一项是能否写出堆元素的完整排序键：优先级、加入序号和任务。第二项是更新与删除时不会直接破坏堆结构。第三项是能否处理重复任务、空队列、已删除堆顶和长期垃圾条目。
回答前需要澄清的问题
- 优先级是数字还是可比较对象？ 默认是可比较的整数，数值越小越优先。
- 任务 ID 是否唯一？ 默认唯一；重复
add视为更新或明确报错。 - 是否需要稳定顺序？ 默认相同优先级按首次加入顺序返回。
- 是否允许惰性删除占用内存？ 允许短期占用，但要说明清理和重建策略。
- 是否并发调用？ 默认单线程；并发版本需要外部锁或线程安全容器。
30 秒回答框架
“我用最小堆保存 [priority, sequence, task]，用字典把任务 ID 映射到当前有效条目。更新先把旧条目标记为 removed，再插入带新序号的新条目；删除同样只标记失效。pop 时持续弹出失效项，直到找到当前条目。序号保证同优先级稳定，字典保证定位 O(1)，堆操作是 O(log n)，惰性条目通过周期性重建控制空间。”
分步骤深入解答
第一步：定义不变量和操作契约
堆顶必须是所有有效条目中最小的 (priority, sequence)。字典只保存每个任务当前条目。一个任务最多有一个有效条目；旧条目可以暂时留在堆中，但不能再次返回。空队列的 pop 返回明确错误或空值，面试时先说明选择。
第二步：选择可比较的堆元素
使用三元组 [priority, sequence, task]。sequence 来自单调计数器，保证两个任务优先级相同仍可比较，同时不会比较任务对象本身。若优先级方向相反，可统一取负值或封装比较器，但不要在不同操作中混用。
第三步：实现 add 和 update
首次 add 生成序号并写入字典与堆。update 先检查任务存在，把旧条目标记为 REMOVED，再插入新条目并覆盖字典指针。这样无需在堆数组中搜索或手动上浮、下沉，操作复杂度保持 O(log n)。
add(task, priority):
if task is active: mark old entry removed
entry = [priority, next(sequence), task]
current[task] = entry
heappush(heap, entry)第四步：实现 remove 和惰性删除
remove 从字典删除任务，并把对应堆条目的任务字段替换为 REMOVED。直接从数组删除会破坏堆结构并需要额外调整。惰性删除让每次修改只触碰一个已知条目，代价是垃圾条目会暂时存在。
第五步：实现 pop 的失效项跳过
循环弹出堆顶；若任务标记为 REMOVED，继续弹出；若字典中的条目不是当前弹出的同一对象，说明它已被更新，也跳过。找到有效条目后从字典删除并返回任务。堆为空时再抛出空队列错误。
第六步：证明复杂度和摊销边界
add、update 和 remove 各执行一次堆插入或标记，时间为 O(log n) 或 O(1) 标记。一次失效条目只会被 pop 弹出一次，因此所有跳过成本可以摊销到产生该条目的更新或删除上。若长期只更新不弹出，空间会增长，需要重建。
第七步：设计重建和空间控制
当堆长度超过有效条目的固定倍数，例如 2 倍，或失效条目超过阈值时，遍历字典保留当前条目并重新建堆。重建是 O(n)，但低频触发后均摊可控。若任务量有明确上限，也可在每次批量更新后清理，避免一次性停顿。
第八步：覆盖边界测试
至少测试空队列、相同优先级稳定顺序、重复更新、删除后 pop、更新后旧条目到达堆顶、全部条目失效、不可比较任务对象和重建前后结果一致。用随机操作与一个排序列表模型对拍，验证每次 pop 的结果相同。
设计取舍与边界
取舍一：惰性删除还是索引堆
惰性删除代码短、修改风险小，适合通用实现；索引堆可以立即删除并控制空间，但需要维护位置映射，交换元素时容易出现 bug。若删除比例极高且内存严格受限，再选择索引堆。
取舍二：单调序号是否会溢出
固定宽度整数可能溢出，导致稳定顺序错误。使用语言提供的无界整数，或在安全时机整体重编号并重建堆。不要在有活动条目时简单把计数器归零。
取舍三：错误还是空值
库函数通常对空队列抛出明确异常，调用方可以区分“没有任务”和“任务值为 null”。若产品接口偏好返回空值，必须在文档中固定语义，并保证任务本身允许的空值不会混淆。
失败演练与演进计划
演练一：连续更新同一任务
对一个任务连续更新 10,000 次，再 pop 并检查只返回最新优先级一次。观察失效条目数量，触发重建后再次确认结果和堆不变量。
演练二：随机混合操作
随机生成 add、update、remove、pop，与简单的字典加排序列表模型对拍。特别检查相同优先级的序号顺序和更新后旧条目不会泄漏。
演练三：异常和资源边界
对不存在任务执行 update/remove，对空队列执行 pop，并在达到内存阈值时触发重建。验证错误类型稳定、重建不会丢任务，且重建期间不会暴露半成品状态。
常见误区与追问
误区一：只存 priority 和 task
任务对象可能不可比较，同优先级时会触发比较错误。必须加入稳定序号或不可比较包装器。
误区二：更新时直接修改堆内元素
修改后元素可能已经不在正确位置，堆不变量会被破坏。应惰性删除旧条目并插入新条目。
误区三：删除时从数组调用 remove
线性查找是 O(n)，随后还要恢复堆结构。用字典定位并标记失效更简单。
误区四：pop 只检查任务字段
更新后的旧条目可能仍带有同一个任务 ID。还要确认弹出的对象等于字典中的当前条目。
误区五：忽略垃圾条目空间
惰性删除不是免费内存。要设置重建阈值并监控堆长度、有效条目数和失效比例。
误区六：没有定义优先级方向
最小堆默认最小值优先。若业务说“数字越大越重要”，应在接口契约中明确转换，避免 add 和 pop 使用相反规则。