云端 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 工具链版本、提交标识和失败操作序列即可，不必保存业务载荷。最终验收结论应明确：这里证明的是串行队列的顺序与边界行为，不包含线程安全、任务执行成功率或调度公平性。把这些边界写清，后续接入执行器时才不会把数据结构测试误当成整个系统的保证。

常见问题