Skip to content

Persistent Mergeable Heap

Persistent mergeable heaps are generally used for solving the \(k\)-th shortest path problem.

If the time complexity of a mergeable heap is not amortized, then after being made persistent, the time complexity of a single operation is guaranteed to be \(O(\log n)\), meaning it will not degenerate due to special data.

Persistent Leftist Tree

Before studying this content, please first understand the related content of Leftist Tree.

Process

Recall the merging process of a leftist tree. Suppose we want to merge two leftist trees with root nodes \(x\) and \(y\), respectively, and the maintained leftist tree satisfies the min-heap property:

  1. If either \(x\) or \(y\) is empty, return \(x+y\).

  2. Choose the node with the smaller value between \(x\) and \(y\) as the root of the merged leftist tree.

  3. Recursively merge the right subtree of \(x\) with \(y\), and set the merged root node as the right child of \(x\).

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

Since each recursion reduces dist[x]+dist[y] by one, and dist[x] is \(O(\log n)\), at most \(O(\log n)\) nodes will be modified in one operation. Thus, the time complexity of this process is \(O(\log n)\).

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

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

  1. If either \(x\) or \(y\) is empty, return \(x+y\).

  2. Choose the node with the smaller value between \(x\) and \(y\), create a copy \(p\) of this node, and use it as the root of the merged leftist tree.

  3. Recursively merge the right subtree of \(p\) with \(y\), and set the merged root node as the right child of \(p\).

  4. Maintain the leftist property of the leftist tree rooted at \(p\), maintain its dist value, and return \(p\).

Since a leftist tree modifies and creates at most \(O(\log n)\) nodes in one operation, let the number of operations be \(m\). Then the time and space complexity of the persistent leftist tree are both \(O(m\log n)\).

Reference Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

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