Convert to it PriorityQueue 拆解【免费下载链接】convertTruly universal online file converter项目地址: https://gitcode.com/GitHub_Trending/convert7/convertConvert to it 敢承诺任何格式转任何格式底气来自在格式图上做路径搜索。支撑这次搜索的是 src/PriorityQueue.ts 约 200 行的数组最小堆。本文拆解 Convert to it PriorityQueue 源码它如何 O(log n) 掏出代价最低的转换候选。为什么万能转换不敢乱搜用户上传 PNG 想要 MP3但没有任何一个 handler 能一步完成。项目把每个转换处理器支持的格式连成有向图src/TraversionGraph.ts 的init()为每种格式建节点、按 handler 能力建边边权来自成本参数——每步基础代价 1DEPTH_COST有损转换 ×1.4图片→视频→音频这类离谱绕行直接罚 10000src/TraversionGraph.ts。searchPath()src/TraversionGraph.ts就在这张图上做 A* 搜索每一步必须从待选候选里掏出当前总代价最小的节点继续扩展。队列容量上限被写死为 15,000,000src/TraversionGraph.ts——设计者预期候选能涨到千万级。这个量级下掏最小值用哪种方式直接决定搜索是几分钟还是几小时取最小值方式取最小插入代价线性扫描O(n)O(1)1 万候选时每步最多比 1 万次有序数组插入O(1)O(n)每次插入都要挪元素数组最小堆O(log n)O(log n)1 万候选约 13 层每层 1 次赋值最小堆是一种用数组装的堆永远能 O(log n) 掏出最小值。这就是searchPath自建PriorityQueue的原因。用一个数组装下整棵堆挖洞上移省下近一半赋值PriorityQueue没有树节点和指针整棵堆隐含在一个普通数组里下标 k 的节点左孩子 2k1右孩子 2k2。对千万级候选逐节点分配对象既慢又吃内存连续数组是缓存友好的现实选择。代价是牺牲随机访问语义contains()只能按引用线性扫描src/PriorityQueue.tstoArray()的顺序也不是优先级顺序。堆只保证堆顶最小其余位置无序这是数组堆的固有取舍。add()的上浮不走原地交换而是先搬家、后落座父节点逐级下移新元素最后一次性放进空位。while (k 0) { const parent (k - 1) 1; if (this._comparator!(item, this._queue[parent]) 0) break; this._queue[k] this._queue[parent]; k parent; }这是siftupUsingComparatorsrc/PriorityQueue.ts的主循环比较结果 ≥ 0 说明新元素不小于父节点堆序已满足停下后把新元素写入this._queue[k]。每层只做 1 次赋值交换写法每层约 3 次含临时变量深度 log2(15,000,000) ≈ 24 层的堆累计省下约 2/3 的写次数。(k - 1) 1用无符号右移代替除法求父下标天然向下取整。把队尾搬到堆顶poll() 如何永远掏出最小值poll()是取最小值的入口拿走堆顶、把最后一个元素挪到堆顶、让它下沉。const s --this._size; const result Tthis._queue[0]; const x Tthis._queue[s]; delete this._queue[s]; if (s ! 0) this.sink(0, x);这是poll()src/PriorityQueue.ts。选最后一个元素补位是因为它已在数组尾部拿走不用挪任何中间元素delete只留一个空洞、不动数组长度下一次add直接覆写避免长度反复伸缩。下沉的循环条件是k halfhalf _size 1下标 ≥ half 的节点必是叶子循环自然停省掉判空分支。每步在左右孩子中选较小的那个上移src/PriorityQueue.ts——第 81 行注释写的是 bigger代码实际选的是较小孩子读源码时别被误导待沉元素 ≤ 较小孩子时 break。一次poll是 O(log n)若换成每次重建堆则是 O(n)千万次 poll 会放大成二次方。若不补位、留空堆顶堆序被破坏之后掏出的不再是最小A* 的贪心前提整个失效。比较器可插拔一个堆同时跑 Dijkstra 和 A*项目里这个类只有两处调用排序规则却不同calculateRemainingCosts()src/TraversionGraph.ts从目标格式倒着做一次 Dijkstra预计算每个节点到目标的剩余代价下界比较器就是a.cost - b.costsearchPath()拿着这份下界做正向 A*const queue new PriorityQueueQueueNode( 1000, (a, b) a.cost remainingCosts[a.index] - (b.cost remainingCosts[b.index]), );见 src/TraversionGraph.ts。比较器编码的是 f g h已走代价加剩余下界。排序规则只是一行 lambda堆本身对 A* 一无所知同一个类两种算法通吃若把比 cost写死在类里A* 就得另写子类。比较器不传也有兜底对toString()结果做localeCompare字典序src/PriorityQueue.ts对象至少有个确定性顺序而不是未定义行为。取舍在于比较器每次操作被调 O(log n) 次必须是 O(1)——上面两处都是纯减法或一次数组下标刚好压线。还有个巧劲某条路径前缀实际转换失败时addDeadEndPath把它记为死路calculateAdaptiveCosts()src/TraversionGraph.ts直接给无穷代价searchPath出队时过滤非有限值src/TraversionGraph.ts。坏候选不必从堆里删——堆内删除指定元素是 O(n) 的脏活一个Infinity就把它挡在门外。给大堆踩一脚刹车分段扩容与 1500 万上限两处调用都显式传入初始容量 1000不传时默认 11构造时容量小于 1 直接抛RangeError。容量用尽后grow()分段处理const oldCapacity this._size; const newCapacity oldCapacity (oldCapacity 64 ? oldCapacity 2 : oldCapacity 1); if (!Number.isSafeInteger(newCapacity)) { throw new RangeError(OOM: new capacity not a safe integer); }这是grow()src/PriorityQueue.ts不足 64 个元素时近似翻倍之后只加 50%。从 11 开始的扩容序列是 11 → 24 → 50 → 102 → 153小堆翻倍减少扩容次数大堆放缓避免把内存预分配过头——百万级元素再翻倍引用内存直接翻倍。数组只增不缩队列清空后容量照样保留这里可以接受因为队列的生命周期就是一次搜索。安全整数检查是最后保险超过 2^53 后数组长度会静默失真与其错下去不如显式抛 OOM。真正的上限不在队列内部而在调用方searchPath发现排队候选达到 15,000,000 就clear()并抛 Conversion path search limit exceededsrc/TraversionGraph.ts把找不到路变成明确报错而不是无限搜索每 1000 次迭代LOG_FREQUENCYsrc/TraversionGraph.ts汇报进度并检查isCancelledUI 想取消随时能停。队列在整条调用链上的位置用户点 Convert 后src/main.ts 调searchPathProxied()TraversionGraph被comlink包进 Web Workersrc/main.ts搜索跑在 Worker 里不卡页面yield 出的路径跨线程传回 UI。整条链上searchPath是循环主体每次add/poll都落在这个 200 行的【免费下载链接】convertTruly universal online file converter项目地址: https://gitcode.com/GitHub_Trending/convert7/convert创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考