1. 题目
实现 StableBoundedPriorityQueue。每项包含 priority、sequence 和 value，优先比较 priority，再比较 sequence。容量为 C 时，push 必须保持最多 C 项；新项比当前最差项更优才替换，否则返回拒绝。pop 返回最优项。
2. 约束与澄清
C必须是正整数；C=0时所有插入都拒绝，不能让数组越界。- 优先级越小越重要；同优先级严格按进入顺序出队。
- “满载拒绝最低优先级”要求能找到最差项；单个最小堆无法在
O(log C)内直接找最差项，因此可维护最小堆和最差项索引，或使用双堆并处理惰性删除。 - 本题先实现单线程版本；并发访问需要外部锁或专门的并发队列。
3. 核心思路
用最小堆保存“下一项”：比较 (priority, sequence)，堆顶就是应出队项。为了在满载时判断最差项，维护一个按 (priority, sequence) 的最大堆；两堆共享条目 ID，删除时采用惰性失效。每个条目只保留一次真实记录，另一堆里的旧节点通过 alive 标记跳过。
如果希望实现更短，可在容量较小或 push 不频繁的场景中线性扫描最差项：出队仍为 O(log C)，插入满载时为 O(C)。面试时先说明这个取舍，再给出双堆优化。
4. 参考实现
record Entry(priority, sequence, value, alive=true)
push(priority, value):
if capacity == 0: return false
candidate = Entry(priority, nextSequence(), value)
if size < capacity:
add candidate to minHeap and maxHeap
size += 1
return true
discard dead nodes from maxHeap
worst = maxHeap.peek()
if (priority, candidate.sequence) >= (worst.priority, worst.sequence):
return false
worst.alive = false
pop maxHeap
add candidate to both heaps
return true
pop():
discard dead nodes from minHeap
if minHeap is empty: return EMPTY
entry = pop minHeap
entry.alive = false
size -= 1
return entry.valuemaxHeap 的键是“越差越大”：优先级越大越差；同优先级时序号越大越晚进入，也越差。若语言没有最大堆，可把键取负，或实现一个比较器。nextSequence 使用单调递增整数，溢出时应采用足够宽的整数或在队列为空时重置。
5. 复杂度与取舍
非满载插入向两个堆各插入一次，复杂度 O(log C)；出队为 O(log C)。满载替换仍为 O(log C)，但惰性删除可能让堆暂时包含失效节点；每个失效节点只会被弹出一次，因此摊销复杂度仍为 O(log C)，空间为 O(C) 的常数倍。线性扫描版本空间更小、代码更短，但满载插入是 O(C)。
6. 验证与观测
C=0、C=1、空队列、连续拒绝和连续替换都要覆盖。- 插入相同优先级的多项，确认
pop顺序与sequence一致。 - 插入优先级更差、相同、更加优的项目，分别检查拒绝、拒绝和替换。
- 随机操作后，将结果与“保存全部元素后按
(priority, sequence)排序并截断 C”的模型比较。 - 记录队列长度、拒绝计数和惰性节点清理次数；拒绝率持续升高时应触发上游限流或负载卸载策略。
7. 常见误区
- 只用
priority排序，导致同优先级项目顺序不稳定。 - 把数值更大的优先级当成更重要，却没有先和面试官确认方向。
- 满载时直接弹出堆顶再插入新项，误删了最优任务。
- 双堆中的失效节点没有清理，
peek读到已被替换的条目。 sequence使用时间戳，时钟回拨或同一毫秒多次插入会破坏 FIFO。
8. 追问及应对
如果要求按租户配额，怎样防止一个租户占满队列？
为每个租户维护计数和上限，插入前同时检查全局容量与租户配额；配额拒绝和全局拒绝分开计数，便于识别热点租户。
如果任务可以取消或更新优先级怎么办？
使用条目 ID 和惰性删除：取消只把 alive 设为假；更新创建新条目并让旧条目失效。出队或查看最差项时清理失效节点，避免在堆中做任意位置删除。
什么时候应改用现成的并发优先队列？
当多个线程或进程同时生产消费、需要阻塞等待或严格内存上限时，优先使用经过验证的并发实现；自制双堆只适合明确的单线程边界和可测试的生命周期。