Skip to content

Leftist Tree

What is a Leftist Tree?

Leftist Tree is a type of mergeable heap, similar to Pairing Heap. It maintains heap properties and supports fast merging.

Definition and Properties of Leftist Trees

For a binary tree, we define an external node as a node with fewer than two children. The \(\mathrm{dist}\) of a node is defined as the number of edges on the path to the nearest external node in its subtree. The \(\mathrm{dist}\) of an empty node is \(0\).

Note

Some references define \(\mathrm{dist}\) as the value described above minus \(1\). This definition simplifies code implementation by omitting some null checks, but it requires initializing the \(\mathrm{dist}\) of empty nodes to \(-1\). In all code examples in this article, the definition of \(\mathrm{dist}\) is the latter one. Please note the difference between the code and the textual definition.

A leftist tree is a binary tree that not only satisfies heap properties but is also "leftist": for each node, the \(\mathrm{dist}\) of its left child is greater than or equal to the \(\mathrm{dist}\) of its right child.

Therefore, the \(\mathrm{dist}\) of each node in a leftist tree equals the \(\mathrm{dist}\) of its right child plus one.

Note that \(\mathrm{dist}\) is not depth; the depth of a leftist tree is not guaranteed. A chain extending to the left also satisfies the definition of a leftist tree.

Core Operation: Merge

When merging two heaps, to maintain heap properties, take the root with the smaller value (for convenience, this article discusses min-heaps) as the root of the merged heap. Then, set the left child of this root as the left child of the merged heap, and recursively merge its right child with the other heap as the right child of the merged heap. To satisfy the leftist property, if the \(\mathrm{dist}\) of the left child is less than the \(\mathrm{dist}\) of the right child after merging, swap the two children.

Reference code:

Implementation 
1
2
3
4
5
6
7
8
9
int merge(int x, int y) {
  if (!x || !y) return x | y;  // If one heap is empty, return the other
  if (t[x].val > t[y].val) swap(x, y);  // Take the smaller value as the root
  t[x].rs = merge(t[x].rs, y);          // Recursively merge the right child with the other heap
  if (t[t[x].rs].d > t[t[x].ls].d)
    swap(t[x].ls, t[x].rs);   // If the leftist property is violated, swap left and right children
  t[x].d = t[t[x].rs].d + 1;  // Update dist
  return x;
}

Due to the leftist property, with each recursive level, the \(\mathrm{dist}\) of the root of one heap decreases by \(1\). For a binary tree with \(n\) nodes, the \(\mathrm{dist}\) of the root does not exceed \(\left\lceil\log (n+1)\right\rceil\). Therefore, merging two heaps of sizes \(n\) and \(m\) has a complexity of \(O(\log n+\log m)\).

Proof of the \(\mathrm{dist}\) Property

A binary tree with root \(\mathrm{dist}\) \(x\) has at least \(x-1\) full levels, meaning it has at least \(2^x-1\) nodes. Note that this property holds for all binary trees, not just leftist trees.

There is an alternative implementation of leftist trees that does not require swapping left and right children: treat the child with the larger \(\mathrm{dist}\) as the left child and the child with the smaller \(\mathrm{dist}\) as the right child.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  int& rs_ref = rs(x);
  rs_ref = merge(rs_ref, y);
  t[x].d = t[rs(x)].d + 1;
  return x;
}

Other Operations on Leftist Trees

Insert Node

A single node can be treated as a heap, so insertion is simply a merge operation.

Delete Root

Merge the left and right children of the root.

Delete Arbitrary Node

Method

First merge the left and right children, then update \(\mathrm{dist}\) from bottom to top, swapping left and right children when the leftist property is violated. Stop recursion when \(\mathrm{dist}\) no longer needs updating.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

// With pushup, simply merging the left and right children deletes the node while maintaining the leftist property
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  int& rs_ref = rs(x);
  rs_ref = merge(rs_ref, y);
  t[rs_ref].fa = x;
  t[x].d = t[rs(x)].d + 1;
  return x;
}

void pushup(int x) {
  if (!x) return;
  if (t[x].d != t[rs(x)].d + 1) {
    t[x].d = t[rs(x)].d + 1;
    pushup(t[x].fa);
  }
}

void erase(int x) {
  int y = merge(t[x].ch[0], t[x].ch[1]);
  t[y].fa = t[x].fa;
  if (t[t[x].fa].ch[0] == x)
    t[t[x].fa].ch[0] = y;
  else if (t[t[x].fa].ch[1] == x)
    t[t[x].fa].ch[1] = y;
  pushup(t[y].fa);
}

Complexity Proof

First consider the merge process. Each step moves \(x\) or \(y\) one level deeper. In the worst case, the right child (the node with the smallest \(\mathrm{dist}\)) of the leftist tree is always chosen, decreasing \(\mathrm{dist}\) by \(1\).

Now consider the pushup process. Let the current node being pushup-ed be \(x\), and its parent be \(y\). The "initial \(\mathrm{dist}\)" of a node is its \(\mathrm{dist}\) before pushup. Starting from the parent of the deleted node, there are two cases:

  1. \(x\) is the right child of \(y\). In this case, the initial \(\mathrm{dist}\) of \(y\) is the initial \(\mathrm{dist}\) of \(x\) plus one.
  2. \(x\) is the left child of \(y\). Since the \(\mathrm{dist}\) of a node can decrease by at most one, recursion continues only when the initial \(\mathrm{dist}\) of \(y\)'s left and right children are equal (in this case, decreasing the left child's \(\mathrm{dist}\) by one causes a swap). Thus, the initial \(\mathrm{dist}\) of \(y\) is still the initial \(\mathrm{dist}\) of \(x\) plus one.

Therefore, the initial \(\mathrm{dist}\) of \(x\) increases by one with each recursive level, so the recursion depth is at most \(O(\log n)\).

Add/Subtract a Value or Multiply by a Positive Number for the Entire Heap

Essentially, any operation that can be lazily tagged without changing relative ordering is permissible.

Apply the tag at the root, and propagate it when deleting the root or merging heaps (when accessing children).

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val > t[y].val) swap(x, y);
  pushdown(x);
  t[x].rs = merge(t[x].rs, y);
  if (t[t[x].rs].d > t[t[x].ls].d) swap(t[x].ls, t[x].rs);
  t[x].d = t[t[x].rs].d + 1;
  return x;
}

int pop(int x) {
  pushdown(x);
  return merge(t[x].ls, t[x].rs);
}

Other Mergeable Heaps

Randomized Heap

Implementation 
1
2
3
4
5
6
7
8
int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[y].val < t[x].val) swap(x, y);
  if (rand() & 1)  // Randomly decide whether to swap left and right children
    swap(t[x].ls, t[x].rs);
  t[x].ls = merge(t[x].ls, y);
  return x;
}

The only difference in this implementation is the use of randomness during merging, eliminating the need for \(\mathrm{dist}\) calculations. The average time complexity is also \(O(\log n)\). For a detailed proof, refer to Randomized Heap.

Skew Heap

A skew heap is an adaptive variant of the leftist tree. When merging two heaps, it unconditionally swaps all nodes along the merge path to attempt to maintain balance. According to amortized analysis, the top-down skew heap has \(O(\log n)\) complexity for insertion, merging, and deletion of the minimum value1.

Example Problems

Template Problems

luogu P3377【Template】Leftist Tree (Mergeable Heap)

Monkey King

Roman Games

Note:

  1. Before merging, check if the two nodes are already in the same heap.
  2. The depth of a leftist tree can reach \(O(n)\), so to find the root of a node's heap, use a union-find set for maintenance instead of traversing parent pointers directly. (Although many problems have weak data and direct traversal may pass...)(When using union-find to maintain roots, ensure the old root points to the new root, and the new root points to itself.)
Reference Code for Roman Games 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>

using namespace std;

constexpr int N = 1000010;

struct Node {
  int val, ls, rs, d;

  Node() {
    val = ls = rs = 0;
    d = -1;
  }

  Node(int v) {
    val = v;
    ls = rs = d = 0;
  }
} t[N];

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val > t[y].val) swap(x, y);
  t[x].rs = merge(t[x].rs, y);
  if (t[t[x].rs].d > t[t[x].ls].d) swap(t[x].ls, t[x].rs);
  t[x].d = t[t[x].rs].d + 1;
  return x;
}

int f[N];

// Find operation
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

bool kill[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int v;
    cin >> v;
    t[i] = Node(v);
    f[i] = i;
  }

  int m;
  cin >> m;
  int x, y;
  char op;
  while (m--) {
    cin >> op;
    if (op == 'M') {
      cin >> x >> y;
      if (kill[x] || kill[y]) continue;
      x = find(x);
      y = find(y);
      if (x != y) f[x] = f[y] = merge(x, y);
    } else {
      cin >> x;
      if (!kill[x]) {
        x = find(x);
        kill[x] = true;
        f[x] = f[t[x].ls] = f[t[x].rs] = merge(t[x].ls, t[x].rs);
        // Since points in the heap will find x, f[x] also needs to be modified
        cout << t[x].val << '\n';
      } else
        cout << "0\n";
    }
  }

  return 0;
}

Tree Problems

「APIO2012」Dispatch

「JLOI2015」City Capture

These problems often involve maintaining a heap at each node, merging with children, and performing operations like popping, modifying, and calculating answers based on the problem requirements, similar to problems involving segment tree merging.

Reference Code for City Capture 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
```cpp
#include <iostream>

using namespace std;

using ll = long long;

constexpr int N = 300010;

struct Node {
  int ls, rs, d;
  ll val, add, mul;

  Node() {
    ls = rs = 0;
    d = -1;
    val = add = 0;
    mul = 1;
  }

  Node(int v) {
    ls = rs = d = 0;
    val = v;
    add = 0;
    mul = 1;
  }
} t[N];

int head[N], nxt[N], to[N], cnt;
int n, m, p[N], f[N], a[N], dep[N], c[N], ans1[N],
    ans2[N];  // p is the heap top corresponding to each node on the tree
ll h[N], b[N];

void add(int u, int v) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  to[cnt] = v;
}

void madd(int u, ll x) {
  t[u].val += x;
  t[u].add += x;
}

void mmul(int u, ll x) {
  t[u].val *= x;
  t[u].add *= x;
  t[u].mul *= x;
}

void pushdown(int x) {  // Similar to lazy propagation in segment tree
  mmul(t[x].ls, t[x].mul);
  madd(t[x].ls, t[x].add);
  mmul(t[x].rs, t[x].mul);
  madd(t[x].rs, t[x].add);
  t[x].add = 0;
  t[x].mul = 1;
}

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val > t[y].val) swap(x, y);
  pushdown(x);
  t[x].rs = merge(t[x].rs, y);
  if (t[t[x].rs].d > t[t[x].ls].d) swap(t[x].ls, t[x].rs);
  t[x].d = t[t[x].rs].d + 1;
  return x;
}

int pop(int x) {
  pushdown(x);
  return merge(t[x].ls, t[x].rs);
}

void dfs(int u) {
  for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
    dep[v] = dep[u] + 1;
    dfs(v);
  }
  while (p[u] && t[p[u]].val < h[u]) {
    ++ans1[u];
    ans2[p[u]] = dep[c[p[u]]] - dep[u];
    p[u] = pop(p[u]);
  }
  if (a[u])
    mmul(p[u], b[u]);
  else
    madd(p[u], b[u]);
  if (u > 1)
    p[f[u]] = merge(p[u], p[f[u]]);
  else
    while (p[u]) {
      ans2[p[u]] = dep[c[p[u]]] + 1;
      p[u] = pop(p[u]);
    }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;

  for (int i = 1; i <= n; ++i) cin >> h[i];

  for (int i = 2; i <= n; ++i) {
    cin >> f[i] >> a[i] >> b[i];
    add(f[i], i);
  }

  for (int i = 1; i <= m; ++i) {
    int v;
    cin >> v >> c[i];
    t[i] = Node(v);
    p[c[i]] = merge(i, p[c[i]]);
  }

  dfs(1);

  for (int i = 1; i <= n; ++i) cout << ans1[i] << '\n';
  for (int i = 1; i <= m; ++i) cout << ans2[i] << '\n';

  return 0;
}
```

「SCOI2011」Tricky Operation

First, use a union-find set to locate the root of a node's heap instead of traversing parent pointers directly.

For single-point queries, if lazy tags are applied normally, one would need to sum tags along the path from the query node to the root, which could be \(O(n)\) in the worst case. If only the heap root has a tag, queries become fast. But how to achieve this?

Use an approach similar to heuristic merging: during each merge, forcibly propagate the tags of the smaller heap to each of its nodes, then use the tag of the larger heap as the tag for the merged heap. Since the merged heap inherits the tag from the other heap, when propagating tags from the smaller heap, subtract the other heap's tag. Since each node's heap size at least doubles after each merge, each node's tags are propagated at most \(O(\log n)\) times, making the total complexity of forced tag propagation \(O(n\log n)\).

For single-point addition, delete the node, update its value, and reinsert it.

For global maximum value, maintain the root of each heap using a balanced tree / heap supporting arbitrary deletion (like leftist tree) / multiset.

Thus, the operations are as follows:

  1. Forcibly propagate tags of the smaller heap, merge the two heaps, update size and tag, and remove the original root that is no longer the root after merging from the multiset.
  2. Delete the node, update its value, reinsert it, and update the multiset. Discuss separately whether the deleted node is the root.
  3. Apply a tag to the heap root and update the multiset.
  4. Apply a global tag.
  5. Query node value + heap root tag + global tag.
  6. Query root value + heap root tag + global tag.
  7. Query maximum value in multiset + global tag.
Reference Code for Tricky Operation 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <set>

using namespace std;

constexpr int N = 300010;

struct Node {
  int val, ch[2], d, fa;

  Node() {
    val = ch[0] = ch[1] = 0;
    d = -1;
    fa = 0;
  }

  Node(int v) {
    val = v;
    ch[0] = ch[1] = d = fa = 0;
  }
} t[N];

int n, m, f[N], tag[N], siz[N], delta;
char op[10];
multiset<int> s;

int& rs(int x) { return t[x].ch[t[t[x].ch[1]].d < t[t[x].ch[0]].d]; }

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (t[x].val < t[y].val) swap(x, y);
  int& rs_ref = rs(x);
  rs_ref = merge(rs_ref, y);
  t[rs_ref].fa = x;
  t[x].d = t[rs(x)].d + 1;
  return x;
}

void pushdown(int x, int y) {
  if (!x) return;
  t[x].val += y;
  pushdown(t[x].ch[0], y);
  pushdown(t[x].ch[1], y);
}

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;

  for (int i = 1; i <= n; ++i) {
    int v;
    cin >> v;
    t[i] = Node(v);
    f[i] = i;
    siz[i] = 1;
    s.insert(v);
  }

  cin >> m;

  while (m--) {
    cin >> op;
    if (op[0] == 'U') {
      int x, y;
      cin >> x >> y;
      x = find(x);
      y = find(y);
      if (x != y) {
        if (siz[x] > siz[y]) swap(x, y);
        pushdown(x, tag[x] - tag[y]);
        f[x] = f[y] = merge(x, y);
        if (f[x] == x) {
          s.erase(s.find(t[y].val + tag[y]));
          tag[x] = tag[y];
          siz[x] += siz[y];
          tag[y] = siz[y] = 0;
        } else {
          s.erase(s.find(t[x].val + tag[y]));
          siz[y] += siz[x];
          tag[x] = siz[x] = 0;
        }
      }
    } else if (op[0] == 'A') {
      if (op[1] == '1') {
        int x, v;
        cin >> x >> v;
        if (x == find(x)) {
          t[t[x].ch[0]].fa = t[t[x].ch[1]].fa = 0;
          int y = merge(t[x].ch[0], t[x].ch[1]);
          s.erase(s.find(t[x].val + tag[x]));
          t[x].val += v;
          t[x].fa = t[x].ch[0] = t[x].ch[1] = 0;
          t[x].d = 1;
          f[x] = f[y] = merge(x, y);
          s.insert(t[f[x]].val + tag[x]);
          if (f[x] == y) {
            tag[y] = tag[x];
            siz[y] = siz[x];
            tag[x] = siz[x] = 0;
          }
        } else {
          t[t[x].ch[0]].fa = t[t[x].ch[1]].fa = t[x].fa;
          t[t[x].fa].ch[x == t[t[x].fa].ch[1]] = merge(t[x].ch[0], t[x].ch[1]);
          t[x].val += v;
          t[x].fa = t[x].ch[0] = t[x].ch[1] = 0;
          t[x].d = 1;
          int y = find(x);
          f[x] = f[y] = merge(x, y);
          if (f[x] == x) {
            s.erase(s.find(t[y].val + tag[y]));
            s.insert(t[x].val + tag[y]);
            tag[x] = tag[y];
            siz[x] = siz[y];
            tag[y] = siz[y] = 0;
          }
        }
      } else if (op[1] == '2') {
        int x, v;
        cin >> x >> v;
        x = find(x);
        s.erase(s.find(t[x].val + tag[x]));
        tag[x] += v;
        s.insert(t[x].val + tag[x]);
      } else {
        int v;
        cin >> v;
        delta += v;
      }
    } else {
      if (op[1] == '1') {
        int x;
        cin >> x;
        cout << t[x].val + tag[find(x)] + delta << '\n';
      } else if (op[1] == '2') {
        int x;
        cin >> x;
        x = find(x);
        cout << t[x].val + tag[x] + delta << '\n';
      } else {
        cout << *s.rbegin() + delta << '\n';
      }
    }
  }

  return 0;
}

「BOI2004」Sequence

This is a paper problem. Refer to 《Huang Yuanhe — Characteristics and Applications of Leftist Trees》.

References

  1. Self-Adjusting Heaps ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用