左式堆：结构
看完你能画出左式堆结构并解释 npl 与左右旋转的设计动机
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
左式堆：结构
看完你能画出左式堆结构并解释 npl 与左右旋转的设计动机
第一印象
见过挂满装饰、一侧沉甸甸的圣诞树吗？枝条全往一边伸，看着歪，却站得稳。左式堆就是这棵「刻意偏斜」的树：堆性质照旧，但形状故意不对称。
树的重载一侧对应堆的左深子树
堆之合并
插入删除二者都擅长，可一旦要合并两个堆，普通二叉堆立刻暴露软肋——这正是左式堆的出场理由。
- 底层是数组，靠下标定位父子
- 合并需把两堆元素全部重排
- n+m 个元素重建，代价 O(n+m)
- 底层是指针树，沿右路径行走
- 合并只拆右路径上的子树
- 右路径长 O(log n)，代价对数级
奇中求正
上一页看到：普通堆合并只能逐个插入，太慢。想让合并快，就得让合并只碰一小部分节点——能不能把树设计成「偏」的，让短的那条路天然可以被沿着走？
重活都堆在左边，右边只留最短的通道供合并快速穿行
NPL：空节点路径长度
上一页看到左式堆「往左沉」的怪长相。但多深才算够左？总得有个尺子。这把尺子叫 npl：从节点出发，走到最近的「缺儿子」位置要几步。
从每个房间到最近安全出口的步数，就是该房间的 npl
NPL 的递归计算
npl(x) 取左右子树 npl 的最小值加一，逐层递归向上算出。
左倾性
每个节点旁标注 NPL 值，对照左右孩子大小，验证左式堆的核心不等式。
自测：npl 判定
一棵二叉树每个节点都满足 npl(左孩子) ≥ npl(右孩子)，能否断定它是合法的左式堆？
左展右敛的形态
这是一棵左式堆：沿左侧越走越深，右侧很快见底，整体左重右轻。
结构性质的推论
上一页我们看到左式堆整体左沉右浅，但这种形态不是巧合，而是每一步插入合并时被强制维持的结果。形态被约束，就有代价可算——最直接的受益者，就是那条最短的右侧路径。
车流集中在右侧快速通过，左侧慢车道再长也不影响通行
收束要点
- ✓合并需求是左式堆一切设计的源头
- ✓NPL 用递归定义：空节点为 0，父为子最小加一
- ✓左倾性保证右孩子 NPL 最短，合并路径 O(log n)
- ✓右路径短靠左倾性，不是靠平衡性
- ✓判断形态：右链长度不超过 O(log n) 即合格
课后思考
先合上笔记自己想一会儿，再对照参考答案。
参考答案关键在合并：合并沿右侧路径走。左倾保证右路径最短，合并代价 O(log n)；若右倾，右侧路径可能长达 O(n)，合并退化为线性。
参考答案左式堆有 npl 保证最坏情形 O(log n)；斜堆只靠均摊分析，单次合并最坏可到 O(n)。左式堆换来的是可预测的性能上界。
参考答案右路径虽短但更新会回溯修改沿途节点，随机访问多、写冲突重。外存场景可考虑按右路径分批缓冲，并发则需沿途加锁或改用无锁结构。