Rank Pairing Heap

Yuxi Luo - CS3393 Algorithms 2 Introduction Initiative Rank Pairing Heap is intended to achieve same time complexity as Fibonacci Heap, but have a simpler structure to implement.

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
Basic Structure Rank Pairing Heap uses binary Half Tree, which is an alternative representation of Heap. For a node in Half Tree, its left child is the first left child in Heap, and its right child is the next sibling. Since a root in a Heap does not have any sibling, the root in Half Tree only have left child.
Half Tree has a property that a node is smaller than any nodes in its left spine.

Min-Heap
Half-Tree

Rank Pairing Heap contains a set of Half Trees which is linked together with a linked list.
Rank Like Fibonacci Heap, Rank Pairing Heap could grow into arbitrary structure. To maintain a reasonable bound on the level of the tree, it introduces a concept of Rank. It is similar to the concept of level. Here introduces a Type 2 Rule of Rank for each node N (Assume that the left child is L, and the right child is R):
  • 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))
Later in Decrease Key operation, all pairs of Half Trees with same Rank will be linked together, so as to reduce the total number of roots. Operations (Assume that every node has distinct value) Find Min Rank Pairing Heap keeps the first root in the root list to be the current minumum value. In the example below, the minimum is marked as black. Insert When inserting a new node, the node itself becomes a new half-tree, and is linked with current root list. If the node contains the current minimum value, it is added to the front of the list.

Union To merge two Rank Pairing Heap, simply merge two root list together, and keep the first root to be the minimum value. Decrease Key To decrease key, there are several steps:
  1. 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)
  2. Split T(N) into two parts: one part is N + T(L), which forms a new Half Tree; the other part is T(R)
  3. Move T(R) to original location of N
  4. Insert the newly-formed Half Tree N + T(L) to the root list
  5. Recalculate Ranks if necessary
Click "refresh" to update the graph from last operations

Extract Min To extract min, there are several steps:
  • 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
After delete min, one-pass linking is performed to reduce the total number of roots. A bucket of Ranks are created to keep track of pairs of Half Trees with same Rank. Link any pairs of Half Trees if possible, and add linked Half Trees to new root list.
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

All operations
Amortization Potential Function The potential function for this analysis consists of two terms: base potential and extra potential, which depend on rank that is calculated by following rules as introduced above:
  • 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))
The paper describes nodes with respect to the rank differences between a node and its two children: based on the rules, there are three types of nodes in Rank Pairing Heap: (1, 1) node, (1, 2) node, and (0, i) node. For example, (1, 1) node means that the node N has two children, for which both of them have rank Rank(N)-1.

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). Amortized Find Min, Insert, and Union This analysis is simple, since those operations takes O(1) constant time, and at most increase the potential by O(1). In total, they still take O(1) time. Amortized Decrease Key Decrease Key is separated into two parts: 1. Decrease the key of the node and perform necessary restructure to place the half tree of the node to the root list. 2. Recalculate the rank.
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). Amortized Extract Min For Extract Min, the true cost depends on the number of half-trees that are merged together, which is at most O(log(n)).
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)). About