雲端 Mac 上的 iOS 穩定優先佇列驗收

圖片預先擷取、待上傳項目與本機任務排序，經常會用到優先佇列。在開發機上連續加入三筆任務，再依序取出，很容易得到正確結果；但到了雲端 Mac 的迴歸測試，加入與取出交錯執行時，同優先級的任務卻開始互換位置。這裡不建置完整的排程器，而是將 Swift 二元堆積獨立出來，驗證它是否始終遵守排序契約。

先定義優先級與穩定性的意義

本文約定：優先級數字越小，越先出列；數字相同時，先入列的先出列。任務識別碼只是業務資料，不參與比較。同一個任務再次入列時，視為新的項目，並取得新的入列序號。

先將這幾條規則寫成測試規格，再實作資料結構。不要拿陣列索引當作永久序號：出列與交換都會改變索引，無法藉此保證穩定性。也不要透過優先級相減來判斷大小，極端整數值可能造成溢位。

穩定性不等於公平性。高優先級任務持續進來時，低優先級任務仍可能長期等待；老化與配額屬於排程策略，不應悄悄混進堆積的比較函式。

以下實作是實值型別，僅供循序存取。整合至並行程式時，應透過單一隔離邊界統一管理，不可讓多個任務同時修改同一個實例。

實作帶有入列序號的最小堆積

將程式碼儲存為 main.swift。比較鍵由優先級與遞增序號組成，入列時的上浮與出列時的下沉都必須使用同一個比較函式，避免兩條路徑對「誰排在前面」有不同的判斷。

struct StableQueue<Value> {
    enum Failure: Error {
        case sequenceExhausted
    }

    private struct Entry {
        let value: Value
        let priority: Int
        let sequence: UInt64
    }

    private var entries: [Entry] = []
    private var nextSequence: UInt64 = 0

    private func precedes(_ a: Entry, _ b: Entry) -> Bool {
        if a.priority != b.priority {
            return a.priority < b.priority
        }
        return a.sequence < b.sequence
    }

    mutating func enqueue(_ value: Value, priority: Int) throws {
        guard nextSequence < UInt64.max else {
            throw Failure.sequenceExhausted
        }
        entries.append(Entry(
            value: value,
            priority: priority,
            sequence: nextSequence
        ))
        nextSequence += 1

        var child = entries.count - 1
        while child > 0 {
            let parent = (child - 1) / 2
            guard precedes(entries[child], entries[parent]) else {
                break
            }
            entries.swapAt(child, parent)
            child = parent
        }
    }

    mutating func dequeue() -> Value? {
        guard !entries.isEmpty else { return nil }
        if entries.count == 1 {
            return entries.removeLast().value
        }

        let result = entries[0].value
        entries[0] = entries.removeLast()
        var parent = 0

        while parent < entries.count / 2 {
            let left = parent * 2 + 1
            let right = left + 1
            var candidate = left
            if right < entries.count,
               precedes(entries[right], entries[left]) {
                candidate = right
            }
            guard precedes(entries[candidate], entries[parent]) else {
                break
            }
            entries.swapAt(parent, candidate)
            parent = candidate
        }
        return result
    }
}

序號到達上限時，明確拋出錯誤，不讓計數器回繞，也不在佇列清空後悄悄歸零。這個實作保留最大值不用，讓失敗發生在修改陣列之前；測試應確認，入列失敗不會改變既有項目的順序。

用交錯操作抓出下沉錯誤

將下列片段接在同一個檔案末尾。它不只檢查最終排序，也驗證取出一筆後再加入同優先級任務時，舊項目仍應排在新項目前面。

func requireEqual<T: Equatable>(_ actual: T, _ expected: T) {
    precondition(actual == expected, "Queue contract failed")
}

var queue = StableQueue<String>()
requireEqual(queue.dequeue(), Optional<String>.none)

try queue.enqueue("A", priority: 2)
try queue.enqueue("B", priority: 1)
try queue.enqueue("C", priority: 2)
requireEqual(queue.dequeue(), Optional("B"))

try queue.enqueue("D", priority: 2)
try queue.enqueue("E", priority: Int.min)
requireEqual(queue.dequeue(), Optional("E"))
requireEqual(queue.dequeue(), Optional("A"))
requireEqual(queue.dequeue(), Optional("C"))
requireEqual(queue.dequeue(), Optional("D"))
requireEqual(queue.dequeue(), Optional<String>.none)

在雲端 Mac 的工作目錄執行：

set -eu
mkdir -p .build
xcrun swiftc -Onone main.swift -o .build/queue-check
.build/queue-check

成功時不會有任何輸出，失敗則以非零結束碼中止作業。這裡不使用 assert，避免檢查在最佳化建置中被移除；也不能拿「編譯成功」取代實際執行驗收。

再補上三組確定性案例：全部同優先級時維持輸入順序；依優先級降冪全部入列後，以升冪順序取出；只有兩個元素時先取出一個，再持續交錯加入與取出。最後一組特別容易暴露右子節點不存在時的越界存取問題。

用參考模型擴大涵蓋範圍

手寫案例能說明契約，卻難以涵蓋所有堆積形狀。參考模型可以直接用陣列儲存「任務編號、優先級、入列序號」，每次取出前依後兩項排序。雖然速度較慢，但實作簡單，適合當作小規模測試的判定基準。

產生交錯操作時，每次入列都同步寫入模型；每次出列則比較兩邊回傳的可選任務編號，操作結束後再將兩邊全部取空。只比較優先級並不足夠，因為同優先級任務交換順序也算缺陷。

使用可指定種子的偽隨機產生器，不要直接依賴無法重現的隨機來源。失敗紀錄至少要包含種子、操作索引、完整的操作前綴，以及兩邊的結果。定位問題時，從失敗前綴中逐段刪除操作，保留仍會失敗的最短序列。

確保參考模型獨立於實作

參考模型不要重用堆積的比較函式，否則同一個錯誤可能讓兩邊同時通過。模型可以先比較優先級，只有相等時才選擇最早入列的項目，直接表達業務規則。

納入迴歸測試並限定結論

提交前固定執行空佇列、單一元素、同優先級穩定性、整數極值與交錯操作測試，再執行一批固定種子的模型比對。新增的失敗種子應納入長期迴歸測試集，不要只是增加隨機測試次數後重新執行。

序號耗盡無法靠一般的入列次數來涵蓋。正式模組可以提供僅供測試使用的內部初始化介面，將計數器設在接近上限的位置，檢查最後一次允許入列與下一次拒絕入列的邊界，避免開放可修改正式環境狀態的公開介面。

封存 Swift 工具鏈版本、提交識別碼與失敗操作序列即可，不必保留業務負載資料。最終驗收結論應明確指出：這裡驗證的是循序存取佇列的順序與邊界行為，不包含執行緒安全、任務執行成功率或排程公平性。將這些邊界寫清楚，後續整合執行器時，才不會把資料結構測試誤當成整個系統的保證。

常見問題