优先级队列左式堆合并操作递归图解
(xa2)左式堆：合并
看完你能亲手画出一个左式堆并写出 npl 与合并的递归全过程
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
优先级队列左式堆合并操作递归图解
(xa2)左式堆：合并
看完你能亲手画出一个左式堆并写出 npl 与合并的递归全过程
: LeftHeap模板类
上一页我们看懂了左式堆怎么合并，这一页把它封装成模板类：结构、接口、核心成员各是什么，什么时候值得用它而不是普通二叉堆。
核心成员
根指针、比较器，节点存左右孩子、npl 与键值
关键接口
merge 为主体，insert 与 deleteMax 都借它实现
模板参数
元素类型 + 比较方式，适配不同键型与优先级语义
典型应用
频繁两两合并的场景：多路归并、可并优先队列
瑞士军刀对应 →LeftHeap模板类
刀身对应 merge 主功能，其余工具（insert/delete）都是折叠在它之上的封装
: 算法
上一页搭好了 LeftHeap 模板类，现在看它的灵魂操作——merge。普通堆合并要把两堆元素倒来倒去，左式堆靠什么绕开这个代价？答案藏在递归里。
递归合并
取较小根作新根，把大根堆与小根的右子树递归合并
交换右子
回溯时若左子 npl 更小，交换左右孩子
复杂度
路径长 O(log n)，合并只需 O(log n) 时间
两支排队队伍插队对应 →左式堆合并
队伍短的排在后面的人先并入长队，再检查队形规则
: 实现
上一页算法告诉我们：比较两堆根、把大的挂到小的右子树上递归合并，右路径太长再交换。这一页看这套流程落到代码上，哪些细节决定它能否长期保持 O(log n)。
递归比较根
大根堆时较大根为新顶，其右子树与另一堆递归合并
挂在右路径
只沿右路径深入，路径长度即递归深度
回溯时检查
合并返回后比较左右子堆 npl，不满足则交换
npl 维护
交换或右子树变更后重算本节点 npl，自底向上传播
登山时走缓坡侧对应 →沿右路径合并
总挑轻的一侧下潜，重物（高 npl）始终压在左边
: 实例
前两页写了 merge 的递归代码，但光看代码难有体感。现在拿两个具体的左式堆走一遍合并，盯住右子树链路怎么被拆开重接，npl 和交换条件何时生效。
选根挂载
比较两堆堆顶，大者作为结果根，小者递归并入其右子堆
沿右链下潜
合并总发生在右子树上，右链最短，递归深度 O(log n)
回溯时检查
逐层返回时若左 npl 小于右 npl，交换左右孩子
npl 更新
交换后重算该节点 npl = 右子树 npl + 1，向上传递
串珍珠的线对应 →右子树链
合并只拆重串最短的那条线，长线（左链）不动
本节要点
- ✓左式堆核心不变量：左子树 npl ≥ 右子树 npl
- ✓合并沿右链进行，递归后必交换左右子树
- ✓右链长度 O(log n)，故合并就是 O(log n)
- ✓npl：节点到最近外部叶节点的最短距离
- ✓插入、删除都可用合并一步表示
延伸主题：斜堆：无 npl 约束的均摊实现二项堆与斐波那契堆对比左式堆的迭代式合并写法
课后思考
三道开放问题，先自己想几分钟，再对照参考答案。
1左式堆合并为何总沿右链走？这保证了什么，又牺牲了什么？
参考答案右链最短，长度不超过 O(log n)，所以合并、插入、删除都由此得 O(log n) 界；牺牲的是树不再平衡，左子树可能很深，但查找类操作本就不是堆的重点。
2n 个节点逐个插入建堆，与两两合并成对归并建堆，复杂度差在哪？
参考答案逐个插入是 n 次 O(log n) 操作，O(n log n)；成对归并像锦标赛，每层总代价 O(n)，共 O(log n) 层，整体 O(n)。批量建堆务必用归并式。
3若把 npl 交换条件去掉、只沿右链合并，会出什么问题？
参考答案右链可能退化成 O(n)，合并退化为线性甚至链状结构，所有操作失去对数界。npl 交换正是维持「右链短」这一不变量的关键。