Persistent meldable heap

Persistent meldable heaps are generally used to solve the $k$-shortest paths problem.

If a meldable heap has non-amortized time complexity, then after persistence the time complexity of each operation is guaranteed to be $O(\log n)$; in other words, special data cannot cause the complexity to deteriorate.

Persistent leftist tree

Before studying this topic, first learn about leftist trees.

Procedure

Recall the merging process for leftist trees. Suppose we want to merge two leftist trees with respective roots $x,y$, and both maintained leftist trees satisfy the min-heap property:

1. If one of the nodes $x,y$ is empty, return $x+y$.

2. Choose the node with the smaller value among $x,y$ as the root of the merged leftist tree.

3. Recursively merge the right subtree of $x$ with $y$, and make the root of the merged tree the right child of $x$.

4. Restore the leftist property of the current merged tree, maintain its dist value, and return the selected root.

Because each recursive call decreases dist[x]+dist[y] by one, while dist[x] is $O(\log n)$, at most $O(\log n)$ nodes are modified in one operation. Thus the time complexity is $O(\log n)$.

Persistence requires retaining historical information so that earlier versions can be accessed later. To make a leftist tree persistent, copy the path modified along the way.

Therefore, the merging process for a persistent leftist tree is as follows:

1. If one of the nodes $x,y$ is empty, return $x+y$.

2. Choose the node with the smaller value among $x,y$, create a copy $p$ of that node, and use it as the root of the merged persistent leftist tree.

3. Recursively merge the right subtree of $p$ with $y$, and make the root of the merged tree the right child of $p$.

4. Restore the leftist property of the tree rooted at $p$, maintain its dist value, and return $p$.

Because a leftist tree modifies and creates at most $O(\log n)$ nodes per operation, if the number of operations is $m$, both the time and space complexity of a persistent leftist tree are $O(m\log n)$.

Reference implementation

int merge(int x, int y) {
  if (!x || !y) return x + y;
  if (v[x] > v[y]) swap(x, y);
  int p = ++cnt;
  lc[p] = lc[x];
  v[p] = v[x];
  rc[p] = merge(rc[x], y);
  if (dist[lc[p]] < dist[rc[p]]) swap(lc[p], rc[p]);
  dist[p] = dist[rc[p]] + 1;
  return p;
}