AIOJ

What Is a Leftist Tree?

Leftist trees, like pairing heaps, are meldable heaps: they satisfy the heap property and support fast merging.

Definition and Properties of Leftist Trees

For a binary tree, define an external node as a node with fewer than two children. Define a node's $\mathrm{dist}$ as the number of edges on the path from it to the nearest external node in its subtree. An empty node has $\mathrm{dist}$ equal to $0$ .

Note

Some sources define $\mathrm{dist}$ as the value $\mathrm{dist}$ in this article minus $1$ . This convention allows the code to omit some null checks, but note that the $\mathrm{dist}$ of an empty node must first be initialized to $-1$ . All code in this article uses the convention that the $\mathrm{dist}$ definition is that an empty node has $\mathrm{dist}$ equal to $-1$ ; keep this difference from the prose $\mathrm{dist}$ definition in mind.

A leftist tree is a binary tree that has both the heap property and the leftist property: the $\mathrm{dist}$ of every node's left child is at least the $\mathrm{dist}$ of its right child.

Consequently, the $\mathrm{dist}$ of every node in a leftist tree equals the $\mathrm{dist}$ of its right child plus one.

Note that $\mathrm{dist}$ is not depth: a leftist tree has no guaranteed depth bound, and a chain extending entirely to the left still satisfies the definition.

Core Operation: Merge

When merging two heaps, the heap property requires us to choose the root with the smaller value (for convenience, this article discusses min-heaps) as the root of the merged heap. Use the chosen root's left child as the merged heap's left child, and recursively merge its right child with the other heap to obtain the merged heap's right child. To satisfy the leftist property, swap the two children if the merged left child's $\mathrm{dist}$ is smaller than the merged right child's $\mathrm{dist}$ .

Reference code:

Implementation

int merge(int x, int y) {
  if (!x || !y) return x | y;  // If one heap is empty, return the other heap
  if (t[x].val > t[y].val) swap(x, y);  // Make the smaller value 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 the left and right children
  t[x].d = t[t[x].rs].d + 1;  // Update dist
  return x;
}

Because of the leftist property, at each recursive level the $\mathrm{dist}$ of the root of one of the heaps decreases by $1$ . In a binary tree with $n$ nodes, the root's $\mathrm{dist}$ is at most $\left\lceil\log (n+1)\right\rceil$ , so merging two heaps of sizes $n$ and $m$ takes $O(\log n+\log m)$ time.

Proof of the

\mathrm{dist}

Property

A binary tree whose root has $\mathrm{dist}$ equal to $x$ has at least $x-1$ full levels, and therefore at least $2^x-1$ nodes. Note that this property holds for all binary trees; it is not specific to leftist trees.

There is another implementation of a leftist tree that does not need to swap the left and right children: treat the child with larger $\mathrm{dist}$ as the left child and the one with smaller $\mathrm{dist}$ as the right child:

Implementation

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

Inserting a Node

A single node can also be regarded as a heap, so simply merge it.

Deleting the Root

Simply merge the root's left and right children.

Deleting an Arbitrary Node

Method

First merge the left and right children, then update $\mathrm{dist}$ from the bottom up, swapping the children whenever the leftist property is violated, and stop recursing when $\mathrm{dist}$ no longer needs updating:

Implementation

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

// With pushup, directly merging the left and right children deletes the node while preserving 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 either $x$ or $y$ down one level. In the extreme case, the right node of the leftist tree (the node with the smallest $\mathrm{dist}$ ) is chosen at every step, so $\mathrm{dist}$ decreases by $1$ .

Now consider the pushup process. Let the current node being processed by pushup be $x$ , and its parent be $y$ . Define a node's initial $\mathrm{dist}$ as its $\mathrm{dist}$ before pushup. Starting the recursion from the parent of the deleted node, there are two cases:

$x$ is the right child of $y$ . Then $y$ 's initial $\mathrm{dist}$ is the initial value of $x$ 's $\mathrm{dist}$ plus one.
$x$ is the left child of $y$ . Since a node's $\mathrm{dist}$ can decrease by at most one, recursion continues only when $y$ 's two children have equal initial $\mathrm{dist}$ values (in which case decreasing the left child's $\mathrm{dist}$ causes the children to be swapped). Therefore, $y$ 's initial $\mathrm{dist}$ is still the initial value of $x$ 's $\mathrm{dist}$ plus one.

Thus, at each recursive level, $x$ 's initial $\mathrm{dist}$ increases by one, so the recursion has depth at most $O(\log n)$ .

Adding/Subtracting a Value from the Entire Heap, or Multiplying by a Positive Number

In fact, any operation that can be represented by a lazy tag without changing the relative order works.

Apply the tag at the root, and push it down when deleting the root or merging heaps (that is, when accessing the children):

Implementation

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 Meldable Heaps

Randomized Heap

Implementation

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 choose whether to swap the 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 that it uses randomness to perform the merge, thereby avoiding the need to compute $\mathrm{dist}$ . Its average time complexity is also $O(\log n)$ ; see Randomized Heap for a detailed proof.

Skew Heap

A skew heap is an adaptive form of a leftist tree. When merging two heaps, it unconditionally swaps every node on the merge path in an attempt to maintain balance. By amortized analysis, the top-down skew heap has $O(\log n)$ complexity for insertion, merging, and deleting the minimum.¹

Example Problems

Template Problems

luogu P3377 Template Leftist Tree (Meldable Heap)

Monkey King

Roman Game

Note the following:

Before merging, check whether the two nodes are already in the same heap.
A leftist tree may have depth $O(n)$ , so use a disjoint-set union structure to maintain the heap containing a node; do not naively jump through its parents. (Although many problem data sets are weak enough that the naive method passes...)(When maintaining roots with DSU, ensure that the original root points to the new root and the new root points to itself.)

Reference Code for Roman Game

#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
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 nodes in the heap resolve to x when find is called, f[x] must also be updated
        cout << t[x].val << '\n';
      } else
        cout << "0\n";
    }
  }

  return 0;
}

Tree Problems

APIO2012 - Dispatch

JLOI2015 - Conquering Cities

Problems of this kind often maintain a heap at each node, merge it with the heaps of its children, and pop, modify, or compute answers according to the problem statement. They are somewhat similar to problems involving segment-tree merging.

Reference Code for Conquering Cities

#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 root corresponding to each node in 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 pushing down a segment-tree tag
  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 Operations

First, use a disjoint-set union structure to find the root of the heap containing a node; do not naively jump upward.

Now consider point queries. With the ordinary way of applying tags, querying the sum of tags along the path from a node to the root can take $O(n)$ time in the worst case. If only the heap root carries a tag, queries can be answered quickly—but how can this be achieved?

Use a method similar to small-to-large merging: whenever two heaps are merged, push the tag of the smaller heap down to every node, and use the tag of the larger heap as the tag of the merged heap. Because the merged heap has the other heap's tag, when pushing down the smaller heap's tag, push down its tag minus the other heap's tag. Since the size of the heap containing a node at least doubles every time the node is merged, each node has its tag pushed down at most $O(\log n)$ times, so the total complexity of pushing tags down naively is $O(n\log n)$ .

For a point addition, delete the node first, update it, and insert it again.

For the global maximum, maintain the root of each heap in a balanced tree, a heap that supports arbitrary-node deletion (such as a leftist tree), or a multiset.

Thus, the operations are as follows:

Push down the tag of the smaller heap by node count, merge the two heaps, update size and tag, and remove from multiset the old root that is no longer the root after merging.
Delete the node, update its value, insert it again, and update multiset. Distinguish whether the deleted node is the root.
Apply a tag to the heap root and update multiset.
Apply a global tag.
Query the value + the heap-root tag + the global tag.
Query the root's value + the heap-root tag + the global tag.
Query the maximum value in multiset + the global tag.

Reference Code for Tricky Operations

#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; see Huang Yuanhe -- Characteristics and Applications of Leftist Trees.

References

Footnotes

Self-Adjusting Heaps ↩