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 設為假；更新建立新項目並讓舊項目失效。出隊或查看最差項時清理失效節點，避免在堆中做任意位置刪除。
什麼時候應改用現成的並行優先佇列？
當多個執行緒或行程同時生產消費、需要阻塞等待或嚴格記憶體上限時，優先使用經驗證的並行實作；自製雙堆只適合明確的單執行緒邊界和可測試的生命週期。