Insert | Union | Find Min | Decrease Key | Extract Min | |

Fibonacci Heap | O(1) | O(1) | O(1) | O(1) amortized | O(log(n)) amortized |
---|---|---|---|---|---|

Rank Pairing Heap | O(1) | O(1) | O(1) | O(1) amortized | O(log(n)) amortized |

Insert | Union | Find Min | Decrease Key | Extract Min | |

Fibonacci Heap | O(1) | O(1) | O(1) | O(1) amortized | O(log(n)) amortized |
---|---|---|---|---|---|

Rank Pairing Heap | O(1) | O(1) | O(1) | O(1) amortized | O(log(n)) amortized |

Half Tree has a property that a node is smaller than any nodes in its left spine.

Rank Pairing Heap contains a set of Half Trees which is linked together with a linked list.

- If it is a leaf, Rank = 0
- If it is a root, Rank = 1 + Rank(L)
- If |Rank(L) - Rank(R)| <= 1: Rank = 1 + Max(Rank(L), Rank(R))
- If |Rank(L) - Rank(R)| > 1: Rank = Max(Rank(L), Rank(R))

- Find the target node N and its corresponding subtree T(N). Assume the left child is L, and right child is R. Therefore, T(N) = N + T(L) + T(R)
- Split T(N) into two parts: one part is N + T(L), which forms a new Half Tree; the other part is T(R)
- Move T(R) to original location of N
- Insert the newly-formed Half Tree N + T(L) to the root list
- Recalculate Ranks if necessary

- Delete the root N of the Half Tree that contains min. Root N has a left child L
- For the remaining subtree T(L), recursively splice right spine of current subtree, and add those right spines to the root list
- Recalculate Ranks if necessary

One minor detail is that the after linking two Half Trees with same Rank, (unlike Fibonacci Heap), the newly-linked Half Tree will not add back to the bucket for future link.

Click "refresh" to update the graph from last operations

- Insert
- Decrease Key
- Extract Min

- If it is a leaf, Rank = 0
- If it is a root, Rank = 1 + Rank(L)
- If |Rank(L) - Rank(R)| <= 1: Rank = 1 + Max(Rank(L), Rank(R))
- If |Rank(L) - Rank(R)| > 1: Rank = Max(Rank(L), Rank(R))

Base potential for a node is the sum of rank differences of its children - 1. For example, (1, 1) node has a base potential of 1+1-1 = 1, (1, 2) node has a base potential of 1+2-1 = 2, and (0, i) node has a base potential of i-1.

Extra potential for a node is defined as 1 for a root, 0 for a (1, 1) node, and 0 for a (1, 2) node or a (0, i) node.

Therefore, the total potential for a node is as follows, and for the entire Rank Pairing Heap is the summation of potentials for all nodes:

- 0: (1, 1) node
- 1: root node
- 2: (1, 2) node
- i-1: (0, i) node

Some of the following amortization depends on the level of the tree. For a root with Rank = k, the size of the half tree is bounded similarly as Fibonacci Heap, for which k <= O(logn).

The true cost depends on the number of nodes for which their ranks need to be recalculated, which is at most O(log(n)).

The first operation should take O(1) time to form a new half tree rooted by the decreased node, and move its original right tree to become the new left child of its parent.

The second operation will decrease ranks for the nodes starting from the parent of the decreased node to maintain above rules. Denote the decreased key N as U1, its left child as U0, and let Ui for i = [2, k] be Ui = parent(Ui-1), such that Uk is either the root or the node that does not decrease in rank.

For each Ui for i = [2, k], the rank differences drop by at most 1, and the base potential drops except for (1, 1) node: (1, 1) => (1, 2); (1, 2) => (1, 1) or (0, 2); (0, i) => (0, i-1). We could show that there are at most 2 (1, 1) nodes along the path of Ui. Suppose Uj is the first (1, 1) node along the path. Rank(Uj) could at most decrease by 1. Suppose Uj' is the second (1, 1) node where j' > j, because Uj'-1's rank drop by 1, Uj' becomes a (1, 2) node, which still satisfies the rules above. Therefore Rank(Uj') = Rank_new(Uj'), and j' = k.

Therefore, along the path of Ui for i = [2, k], the total potential drops by k - 1 (from the new half-tree of N that is added to the root list) - 3 (since i starts from 2 instead of 0) - 2 (from the two (1, 1) node) = k - 6.

In total, the amortized cost for Decrease Key is therefore O(log(n) - log(n) + 6) = O(1).

There are at most O(log(n)) original (1, 1) nodes on the right spine of the half-tree rooted by L(N) to become a new half-tree. Therefore, the total potential increases by at most O(log(n)).

In total, the amortized cost for Extract Min is therefore O(log(n) + log(n)) = O(log(n)).

- Github Repo: Rank-Pairing-Heap
- Graph Drawing Tool: Cytoscape
- Original Paper: Rank-Pairing Heaps by Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan