Convert to it PriorityQueue 拆解

Convert to it PriorityQueue 拆解

【免费下载链接】convertTruly universal online file converter项目地址: https://gitcode.com/GitHub_Trending/convert7/convert

Convert to it 敢承诺"任何格式转任何格式"，底气来自在格式图上做路径搜索。支撑这次搜索的，是 src/PriorityQueue.ts 约 200 行的数组最小堆。本文拆解 Convert to it PriorityQueue 源码：它如何 O(log n) 掏出代价最低的转换候选。

为什么"万能转换"不敢乱搜

用户上传 PNG 想要 MP3，但没有任何一个 handler 能一步完成。项目把每个转换处理器支持的格式连成有向图：src/TraversionGraph.ts 的init()为每种格式建节点、按 handler 能力建边，边权来自成本参数——每步基础代价 1（DEPTH_COST），有损转换 ×1.4，"图片→视频→音频"这类离谱绕行直接罚 10000（src/TraversionGraph.ts）。

searchPath()（src/TraversionGraph.ts）就在这张图上做 A* 搜索，每一步必须从待选候选里掏出"当前总代价最小"的节点继续扩展。队列容量上限被写死为 15,000,000（src/TraversionGraph.ts）——设计者预期候选能涨到千万级。这个量级下，"掏最小值"用哪种方式，直接决定搜索是几分钟还是几小时：

最小堆是一种用数组装的堆：永远能 O(log n) 掏出最小值。这就是searchPath自建PriorityQueue的原因。

用一个数组装下整棵堆：挖洞上移省下近一半赋值

PriorityQueue没有树节点和指针，整棵堆隐含在一个普通数组里：下标 k 的节点，左孩子 2k+1，右孩子 2k+2。对千万级候选，逐节点分配对象既慢又吃内存，连续数组是缓存友好的现实选择。代价是牺牲随机访问语义：contains()只能按引用线性扫描（src/PriorityQueue.ts），toArray()的顺序也不是优先级顺序。堆只保证堆顶最小，其余位置无序，这是数组堆的固有取舍。

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; }

这是siftupUsingComparator（src/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 = <T>this._queue[0]; const x = <T>this._queue[s]; delete this._queue[s]; if (s !== 0) this.sink(0, x);

这是poll()（src/PriorityQueue.ts）。选"最后一个元素"补位，是因为它已在数组尾部，拿走不用挪任何中间元素；delete只留一个空洞、不动数组长度，下一次add直接覆写，避免长度反复伸缩。

下沉的循环条件是k < half（half = _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.cost；
• searchPath()拿着这份下界做正向 A*：

const queue = new PriorityQueue<QueueNode>( 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 exceeded"（src/TraversionGraph.ts），把"找不到路"变成明确报错而不是无限搜索；每 1000 次迭代（LOG_FREQUENCY，src/TraversionGraph.ts）汇报进度并检查isCancelled，UI 想取消随时能停。

队列在整条调用链上的位置

用户点 Convert 后，src/main.ts 调searchPathProxied()；TraversionGraph被comlink包进 Web Worker（src/main.ts），搜索跑在 Worker 里不卡页面，yield 出的路径跨线程传回 UI。整条链上，searchPath是循环主体，每次add/poll都落在这个 200 行的

【免费下载链接】convertTruly universal online file converter项目地址: https://gitcode.com/GitHub_Trending/convert7/convert