Proofs: Rank-pairing heap

Amortized cost of the type-2 rank-pairing heap full

This proof shows: time.amortized.

We prove Theorem 6.1 of Haeupler, Sen and Tarjan for type-2 rank-pairing heaps with multipass linking: find-min, insert, meld and decrease-key take $O(1)$ amortized time, and delete-min takes $O(\log n)$ amortized time. The proof follows the paper, with the accounting written out.

The rank bound. A child of rank $k$ has at least $F_{k+3} - 1$ nodes in its subtree, with $F_0 = 0$, $F_1 = 1$. By induction on height: a missing node of rank $-1$ has $0 = F_2 - 1$ nodes, and a leaf has $1 = F_3 - 1$. A 0,$i$-node of rank $k$ has a child of rank $k$, and so at least $F_{k+3} - 1$ nodes. A 1,1- or 1,2-node of rank $k$ has children of ranks at least $k - 1$ and $k - 2$, so at least $1 + (F_{k+2} - 1) + (F_{k+1} - 1) = F_{k+3} - 1$ nodes. A root of rank $k$ has a left child of rank $k - 1$, so its half tree has at least $F_{k+2} \ge \varphi^k$ nodes. So every rank is at most $\log_\varphi n$.

The potential. For a node $x$, let $\sigma(x)$ be the sum of the rank differences of its children, where a missing child counts with its rank $-1$, but the missing right child of a root does not count. Let $\psi(x) = \sigma(x) - 1$ for every node. For a root, $\sigma(x) = 1$ and $\psi(x) = 0$. Define the potential of a node as $\phi(x) = 1$ for a root, $\phi(x) = 0$ for a 1,1-node, and $\phi(x) = \sigma(x) - 1$ for every other non-root. This is the potential of the paper: a root with a 1-child has potential 1, a 1,1-node has 0, and an $i,j$-node other than a 1,1-node has $i + j - 1$. Every $\phi(x) \ge 0$: a 1,2-node has 2, and a 0,$i$-node with $i > 1$ has at least 1. Let $\Phi$ be the sum over all nodes. The empty heap has $\Phi = 0$.

Count one unit of time for each operation, each half tree processed in delete-min, each link and each iteration of the rank-reduction loop.

Insert, meld, find-min. Insert adds a root, $\Delta\Phi = 1$, so the amortized cost is 2. Meld and find-min do not change $\Phi$.

Delete-min. Deleting the root $z$ lowers $\Phi$ by 1. The disassembly makes each node on the right spine of $z.left$ a root, with $\phi = 1$. Each spine node that was not a 1,1-node had $\phi \ge 1$, and its children do not change, so its potential does not increase. For a 1,1-node $s$ on the spine, its right child, the next spine node, has rank $r(s) - 1$. Ranks along the spine never increase, because rank differences are not negative. So the 1,1-nodes on the spine have distinct ranks, all less than $r(z) \le \log_\varphi n$, and there are at most $\log_\varphi n$ of them. The disassembly raises $\Phi$ by at most $\log_\varphi n$.

Let $h$ be the number of half trees after the disassembly. The rest of the operation takes $h + O(1)$ units plus one per link. Each link turns a root ($\phi = 1$) into a 1,1-node ($\phi = 0$) and does not change the children of any other node, except that the winner gets a new left child. The winner is a root, with $\phi = 1$ before and after. So each link lowers $\Phi$ by 1, which pays for the link. After multipass linking, the roots have distinct ranks in $\{0, \ldots, \lfloor \log_\varphi n \rfloor\}$, so at most $\log_\varphi n + 1$ remain, and there were at least $h - \log_\varphi n - 1$ links. The amortized cost is at most

Decrease-key. If $x$ is a root, the cost is 1 and $\Phi$ does not change. Otherwise let $u_1 = u$ be the parent of $x$, let $y$ be its right child, and let $u_1, u_2, \ldots, u_m$ be the non-roots whose ranks decrease, in this order; $u_{i+1}$ is the parent of $u_i$. Let $\delta_i \ge 1$ be the decrease at $u_i$, and let $w$ be the node at which the loop ends (a non-root whose rank does not change, or a root).

Claim A: at most one of $u_1, \ldots, u_m$ is a 1,1-node before the operation, and every $\delta_i$ after the first 1,1-node among them is 1. A 1,1-node of rank $k$ has children of rank $k - 1$; if one of them loses rank, $f$ gives $k$ (if the child has rank $k - 2$) or $k - 1$ (if less), so a 1,1-node decreases by at most 1. By Lemma 2 of the correctness proof, a node whose child decreased by 1 decreases by at most 1. So once a 1,1-node $t$ decreases, every later decrease is by exactly 1. A later 1,1-node whose child decreases by exactly 1 has children of ranks $k - 1$ and $k - 2$, so $f = k$ and it does not decrease. So it is $w$, not one of the $u_i$.

Accounting. Let $\Psi = \sum_x \psi(x)$ over all nodes, where $\psi(x) = \sigma(x) - 1$ for every node, root or not. Let $N$ be the number of 1,1-nodes. Since $\phi(x) = \psi(x)$ for all nodes except 1,1-nodes and roots, and $\phi = \psi - 1$ for a 1,1-node and $\phi = \psi + 1$ for a root, we have $\Phi = \Psi - N + R$, where $R$ is the number of roots.

• $\Delta R = +1$ (the root $x$).
• $-\Delta N$ is at most the number of nodes that stop being 1,1-nodes. Only nodes whose children's rank differences change can change type: $x$, the $u_i$, and $w$. By Claim A at most one $u_i$ is a 1,1-node. So $-\Delta N \le 3$.
• $\Delta\Psi$. Before, $\psi(x) = \Delta(x.left) + \Delta(y) - 1$, where $\Delta(y) = r(x) - r(y)$; after, $x$ is a root, with $\psi(x) = 0$. When $y$ replaces $x$ as a child of $u_1$, the rank difference of that child of $u_1$ grows from $\Delta(x)$ to $\Delta(x) + \Delta(y)$, so $\psi(u_1)$ grows by $\Delta(y)$. When the rank of $u_i$ drops by $\delta_i$, the rank differences of both its children drop by $\delta_i$, so $\psi(u_i)$ drops by $2\delta_i$, and the rank difference of $u_i$ as a child of $u_{i+1}$ (or of $w$) grows by $\delta_i$, which raises $\psi$ of the parent by $\delta_i$. If $w$ is a root, its rank is reset to make it a 1-node, so $\psi(w) = 0$ before and after the operation. Adding up,

because $\Delta(x.left) \ge 0$ and every $\delta_i \ge 1$.

So $\Delta\Phi \le (1 - m) + 3 + 1 = 5 - m$. The actual cost is 1 for the cut and $m + 1$ for the iterations of the loop. The amortized cost of decrease-key is at most $(m + 2) + (5 - m) = 7$, which is $O(1)$. $\blacksquare$

The rank-pairing heap operations keep half order and the type-2 rank rule full

This proof shows: correctness.

We use the definitions of the page. A missing child has rank $-1$. For integers $a$ and $b$, let $f(a, b) = \max(a, b)$ if $|a - b| > 1$ and $f(a, b) = \max(a, b) + 1$ if $|a - b| \le 1$. The invariants are (1) half order: the key of each node is at most every key in its left subtree, and every root has no right child; (2) the type-2 rank rule: every root $x$ has $r(x) = r(x.left) + 1$, and every non-root is a 1,1-, 1,2- or 0,$i$-node with $i > 1$.

Lemma 1 (the rule fixes the rank). A non-root $u$ with children of ranks $a$ and $b$ obeys the type-2 rule if and only if $r(u) = f(a, b)$.

Proof. Let $a \ge b$. If $r(u) = a + 1$ and $a - b \le 1$, the rank differences are $1$ and $1$ or $1$ and $2$. If $r(u) = a$ and $a - b > 1$, they are $0$ and $a - b > 1$. Conversely, a 1,1- or 1,2-node has $r(u) = a + 1$ with $a - b \in \{0, 1\}$, and a 0,$i$-node with $i > 1$ has $r(u) = a$ with $a - b = i > 1$. In each case $r(u) = f(a, b)$. $\square$

Lemma 2 (monotone). $f$ does not decrease when one argument increases by one, and it increases by at most one.

Proof. Fix $b$ and compare $f(a, b)$ with $f(a + 1, b)$. If $a + 1 \le b - 2$, both are $b$. If $a + 1 = b - 1$, they are $b$ and $b + 1$. If $a + 1 \in \{b, b + 1\}$, they are $b + 1$ and $b + 1$ when $a + 1 = b$, and $b + 1$ and $b + 2$ when $a + 1 = b + 1$. If $a \ge b + 1$, then $a + 1 \ge b + 2$, so $f(a + 1, b) = a + 1$, and $f(a, b) \in \{a, a + 1\}$. In every case the increase is 0 or 1. The function is symmetric. $\square$

Lemma 3 (link). If $x$ and $y$ are roots of half trees of equal rank $k$ that satisfy (1) and (2), LINK$(x, y)$ returns the root of a half tree of rank $k + 1$ that satisfies (1) and (2).

Proof. After line L1, $x.key \le y.key$. The new left subtree of $x$ holds $y$, the left subtree of $y$, and the old left subtree of $x$. Every key there is at least $x.key$: the first two because $y.key \ge x.key$ and by half order at $y$, the third by half order at $x$. The left subtree of $y$ did not change. The ranks of the two children of $y$ are $r(y.left) = k - 1$ and $r(\text{old } x.left) = k - 1$, so $y$ is a 1,1-node. The root $x$ now has rank $k + 1 = r(y) + 1$, so it is a 1-node and has no right child. $\square$

Theorem 1 (insert, meld, delete-min). These operations keep (1) and (2), and delete-min returns a smallest key.

Proof. Insert adds a one-node half tree of rank $0 = -1 + 1$. Meld only joins root lists. In delete-min, each root holds the smallest key of its half tree, because the root has no right child and its left subtree holds all other nodes, so $z = H.min$ holds a smallest key. Line L4 removes $z$ and cuts the right spine $s_1 = z.left, s_2 = s_1.right, \ldots$. Each $s_i$ keeps its left subtree, so half order holds in the new half tree rooted at $s_i$, which has no right child, and $r(s_i) = r(s_i.left) + 1$ makes it a 1-node. Nodes inside the left subtrees do not change. The links of lines L5 and L6 join only half trees of equal rank, so they keep (1) and (2) by Lemma 3. $\square$

Theorem 2 (decrease-key). DECREASE-KEY keeps (1) and (2).

Proof. If $x$ is a root, its key is at most every key in its left subtree before the change, and so also after it. Otherwise let $u$ be the parent of $x$ and $y$ its right child.

Half order after line L9. Let $v$ be any node other than $x$. If $x$ was in the left subtree of $v$, then so were $y$ and its subtree; after line L9 the left subtree of $v$ is the old one without $x$ and the left subtree of $x$. So it lost keys and gained none, and half order at $v$ holds. Otherwise the left subtree of $v$ did not change. At $x$, every key of its left subtree was at least the old key of $x$, which is at least the new key. So half order holds everywhere, and $x$ is a root with no right child.

The rank rule. Line L9 sets $r(x) = r(x.left) + 1$, so the new root is a 1-node. The nodes in the subtrees of $x.left$ and $y$ did not change. The only node whose children changed is $u$: its child $x$, of rank $r(x)$, was replaced by $y$, of rank $r(y) \le r(x)$, because rank differences are not negative. We prove by induction over the iterations of lines L10 to L14 this claim: at the start of an iteration with node $u$, every node other than $u$ obeys the rule, and the ranks of the children of $u$ are at most what they were when $u$ last obeyed the rule.

If $u$ is a root, line L11 makes it a 1-node, and the rule holds everywhere. Otherwise let $k = f(r(u.left), r(u.right))$. When $u$ last obeyed the rule, $r(u)$ was $f$ of the old ranks of its children, by Lemma 1. The rank of $u$ has not changed since then, and by Lemma 2 $f$ does not increase when the arguments decrease, so $k \le r(u)$. If $k = r(u)$, line L13 returns, and $u$ obeys the rule by Lemma 1. If $k < r(u)$, line L14 sets $r(u) = k$, so $u$ obeys the rule. Its parent now has a child of smaller rank, and every other node obeys the rule, so the claim holds for the next iteration with the parent of $u$. Each iteration goes one level up, so the loop ends, at a root or at line L13. $\blacksquare$