左偏树(可并堆)

What · 是什么

左偏树（Leftist Tree）是一种可并堆（mergeable heap）：在二叉堆的堆性质（父节点值 ≤ 子节点值，小根堆）之上，额外维护每个节点的 dist（到子树中最近『外节点』——即子节点数小于 2 的节点——经过的边数），并保证『左偏性质』：每个节点左儿子的 dist ≥ 右儿子的 dist。因此每个节点的 dist 等于其右儿子 dist 加一，且根的 dist 为 O(log n)。核心操作 merge 将两棵左偏树在 O(log n + log m) 内合并，其他操作（插入=与单点合并、删根=合并左右儿子、删任意节点=合并儿子+自底向上 pushup）都归约为 merge。由于每次递归使其中一个根 dist 减一，复杂度有保证。它是竞赛中实现可并堆（如 k 短路、树上合并堆）的最常用结构，也可持久化。

Why · 为什么

How · 实现

伪代码

dist(空)=-1, dist(外节点)=0, dist(x)=dist(right(x))+1
merge(x, y):
  if x 为空: return y
  if y 为空: return x
  if val(x) > val(y): swap(x, y)   # 取小根为根
  right(x) = merge(right(x), y)
  if dist(left(x)) < dist(right(x)): swap(left(x), right(x))
  dist(x) = dist(right(x)) + 1
  return x
insert(root, v) = merge(root, new_node(v))
pop_min(root)   = merge(left(root), right(root))

Python 实现

import heapq
import random
import sys
sys.setrecursionlimit(1000000)


class Node:
    __slots__ = ('val', 'l', 'r', 'dist')

    def __init__(self, val):
        self.val = val
        self.l = None
        self.r = None
        self.dist = 0   # 外节点 dist=0，空节点视为 -1


def _d(x):
    return -1 if x is None else x.dist


def merge(x, y):
    """合并两棵左偏树（小根堆），返回新根。O(log n + log m)"""
    if x is None:
        return y
    if y is None:
        return x
    if x.val > y.val:
        x, y = y, x
    x.r = merge(x.r, y)
    if _d(x.l) < _d(x.r):
        x.l, x.r = x.r, x.l
    x.dist = _d(x.r) + 1
    return x


def insert(root, val):
    return merge(root, Node(val))


def pop_min(root):
    """删除并返回堆顶。返回 (新根, 原堆顶值)；空堆返回 (None, None)"""
    if root is None:
        return None, None
    return merge(root.l, root.r), root.val


if __name__ == '__main__':
    # 与 heapq 交叉验证（随机操作序列）
    random.seed(1)
    h = None
    ref = []
    for _ in range(5000):
        op = random.random()
        if op < 0.5 or not ref:
            v = random.randint(0, 100000)
            h = insert(h, v)
            heapq.heappush(ref, v)
        else:
            h, m = pop_min(h)
            r = heapq.heappop(ref)
            assert m == r, (m, r)
        if h is None:
            assert not ref
    # 双堆合并验证
    h1 = h2 = None
    r1, r2 = [], []
    for v in [3, 1, 4, 1, 5, 9, 2, 6]:
        h1 = insert(h1, v); r1.append(v)
    for v in [7, 0, 8, 5, 2]:
        h2 = insert(h2, v); r2.append(v)
    h = merge(h1, h2)
    r = sorted(r1 + r2)
    out = []
    while h is not None:
        h, m = pop_min(h)
        out.append(m)
    assert out == r, (out, r)
    print('leftist tree: All tests passed.')

易错点

• 找堆顶必须用并查集：左偏树深度可能 O(n)，直接跳父会 TLE/爆栈
• merge 前先判断两堆是否已在同一堆中（若已在则直接返回，否则死循环）
• dist 定义要统一：OI Wiki 用空节点 dist=-1（代码免判空），用 dist=0 的定义则空节点必须特判
• 用对象实现时递归深度可能到 O(n)（左链），需 sys.setrecursionlimit；竞赛中建议数组模拟
• 删除任意节点需要 parent 指针和自底向上 pushup，只 merge 左右儿子会破坏该节点父节点的左偏性质
• pop_min 返回值顺序写反（先返回新根后返回值）；空堆需特判

例题

信源

• OI Wiki✓ https://oi-wiki.org/ds/leftist-tree/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/ds/leftist-tree.md
• OI Wiki✓ https://oi-wiki.org/ds/heap/