左式堆

左式堆

不需要搜索，因此不需要平衡。

合并

思路：沿着右藤遍历并进行二路归并，每次取两堆中较小的节点连接，左子树不变。 时间复杂度渐近等于右侧藤长度。 如何控制藤长？

NPL

定义 npl 为当前节点到最近的空节点的距离。 在保持堆序性的基础上，保证 $npl(lc)\ge npl(rc)$，即倾向于在左子树尽可能多地分配节点。

• ! 左子树的规模和高度不一定大于右子树

有 $npl(x)=npl(rc(x))+1$

右侧藤长度为 $d$ 的左式堆至少包含高度为 $d$ 的满子树，即包含至少 $2^{d+1}-1$ 个节点。 反过来，包含 $n$ 个节点的左式堆，右侧藤长度 $d\le {\log }_2(n+1)-1=O(\log n)$

实现

递归实现：

• 若其中之一为空，返回另一子树。
• 保证 $a$ 节点大于 $b$ 节点（否则交换）
• 将原来的 $a$ 的右子树和 $b$ 继续递归地进行合并并接回作为 $a$ 的新右子树
• 回溯时，保证左子树的 npl 大于等于右子树（否则交换），更新当前节点的 npl 时间复杂度为 $O(\log n)$

插入

视为原堆和单节点的合并

删除

删去根后将左右子树合并