图 1：依赖图加大根堆，高权重任务尽量往前排。
先说明属性：这是一篇笔试真题复盘，题目出自本地历史笔试资料，与任何公司的当前招聘无关。题目要求对带权的有向无环图（DAG）排序：不违背依赖关系，且权重大的任务尽量靠前。它在 Agent 任务编排、数据管线调度里天天出现——「依赖约束加优先级」几乎是最常见的排序需求。考点不是 Kahn 算法本身，而是把队列换成大根堆这一步。
先回顾普通拓扑排序在做什么。
Kahn 算法的骨架：统计每个节点的入度，把所有入度为 0 的节点放进一个「可用集合」，每次从中取一个输出，删掉它的出边让后继入度减 1，凡减到 0 的立刻加入可用集合，循环直到取完。它能给出任意一个合法拓扑序，但「取哪一个」是随意的——用普通队列实现时，先解锁的先出，权重完全不参与决策。
本题的要求恰恰是把权重拉进决策：在每个位置上，从当前可用集合里挑权重最大的。这一步改动极小——把队列换成按权重排序的大根堆——但性质完全不同。
为什么这个贪心是安全的。
关键是想清楚「可用集合」的含义：入度为 0 意味着这个任务的所有前置依赖都已排定，此刻选它不违背任何约束。既然选谁对合法性无影响，那就应该选「当前最重要」的——把权重大的往后拖没有任何好处，只会让它错失更早的位置。每一步都取当前可用集合的权重最大者，得到的就是贪心意义下最优的拓扑序。这也是这类题的通用范式：约束条件交给拓扑序保证，优化目标交给堆来贪心。
手工推演一遍。
用这张图里的例子：五个任务 A(9)、B(5)、C(7)、D(8)、E(3)，依赖关系 A→C、A→D、B→D、C→E、D→E。初始入度为 0 的是 A 和 B，入堆。
第一步：堆里 {A9, B5}，弹出权重最大的 A；A 的后继里 C 的入度归零入堆，D 还差 B 没排。第二步：堆里 {B5, C7}，弹出 C——注意 C 虽后入堆但权重更大，这正是换堆的意义；C 的后继 E 还差 D，无人解锁。第三步：堆里只剩 {B5}，弹出 B，D 的两个前置终于齐了，入堆。第四步：弹出 {D8}，E 解锁入堆。第五步：弹出 E，结束。最终序列 A → C → B → D → E：依赖全部满足，且在第二步确实把更重的 C 提到了 B 前面。
代码实测。
用 Node.js 22.15.0 运行（node topoheap.js），除了上面的例子，再拿一道只含数字编号的原题样例交叉验证：
class MaxHeap {
constructor() { this.a = []; }
push(x) { this.a.push(x); let i = this.a.length - 1;
while (i > 0) { const p = (i - 1) >> 1;
if (this.a[p].w >= this.a[i].w) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p; } }
pop() { const top = this.a[0], last = this.a.pop();
if (this.a.length) { this.a[0] = last; let i = 0;
for (;;) { let l = 2 * i + 1, r = l + 1, m = i;
if (l < this.a.length && this.a[l].w > this.a[m].w) m = l;
if (r < this.a.length && this.a[r].w > this.a[m].w) m = r;
if (m === i) break; [this.a[m], this.a[i]] = [this.a[i], this.a[m]]; i = m; } }
return top; }
get size() { return this.a.length; }
}
function weightedTopo(nodes, edges) {
const indeg = new Map(nodes.map(n => [n.id, 0]));
const adj = new Map(nodes.map(n => [n.id, []]));
for (const [s, t] of edges) { adj.get(s).push(t); indeg.set(t, indeg.get(t) + 1); }
const heap = new MaxHeap();
for (const n of nodes) if (indeg.get(n.id) === 0) heap.push(n);
const order = [];
while (heap.size) {
const cur = heap.pop(); order.push(cur.id);
for (const nxt of adj.get(cur.id)) {
indeg.set(nxt, indeg.get(nxt) - 1);
if (indeg.get(nxt) === 0) heap.push(nodes.find(n => n.id === nxt));
}
}
return order;
}
const nodes = [{ id: "A", w: 9 }, { id: "B", w: 5 }, { id: "C", w: 7 },
{ id: "D", w: 8 }, { id: "E", w: 3 }];
const edges = [["A","C"],["A","D"],["B","D"],["C","E"],["D","E"]];
console.log("带权示例:", weightedTopo(nodes, edges).join(" "));
// 交叉验证：4 节点权重 2/3/5/4，边 1→2 1→3 2→4 3→4，期望 1 3 2 4
const n2 = [{id:"1",w:2},{id:"2",w:3},{id:"3",w:5},{id:"4",w:4}];
const e2 = [["1","2"],["1","3"],["2","4"],["3","4"]];
console.log("交叉样例:", weightedTopo(n2, e2).join(" "));
实测输出：
带权示例: A C B D E
交叉样例: 1 3 2 4
两组输出与手工推演完全一致。交叉样例里节点 3 权重 5 大于节点 2 的 3，所以 1 之后先排 3——和带权示例第二步的逻辑一模一样。
图 2：五步推演表——堆里永远弹当前可用的最大权重。
收尾：复杂度与变形。
每个节点入堆出堆各一次，每条边只扫一遍，堆操作 O(log V)，总复杂度 O((V + E) log V)，相对普通 Kahn 只多一个对数因子。两个常见追问要有准备：一是这个贪心是「尽量」而非全局最优——它保证每个位置取当前最优，不保证某种全局指标最优，题目措辞也是「尽量先执行」；二是变形「字典序最小的拓扑序」用的是同一个模子，只是把大根堆换成按编号的小根堆，骨架一行不改。
答题建议顺序：先复述 Kahn 的可用集合概念，再指出「取谁」是自由度所在，给出大根堆改造与贪心安全性论证，最后补复杂度与字典序变形。能主动讲清「约束归拓扑序、优化归堆」这条分工线的答案，通常能直接过关。你在工程里遇到过「依赖约束加优先级」的调度需求吗？最后是用堆实现的，还是干脆上了调度框架？欢迎分享。