Proofs: Relaxed heap

The relaxed heap of this page keeps the binomial shape and invariants (a) to (c), and FIX ends full

This proof shows: correctness.

We use the definitions of the page. A non-root node $v$ is a violation if $v.key < p.key$ for its parent $p$. A stale mark is a mark on a node that is not a violation. The invariants are (S) every node of rank $k$ has children of the ranks $0, \ldots, k - 1$ in the slots $0, \ldots, k - 1$, the parent pointers agree with the slots, the roots have different ranks and are not active, and the table of active nodes holds exactly the active nodes under their current ranks; (a) at most one active node of each rank; (b) every active node is a last child; (c) every non-root node that is not active is not a violation.

Lemma 1 (links). Let $a$ and $b$ be roots of equal rank $k$ that are not active and are not in any tree. LINK$(a, b)$ returns a tree of rank $k + 1$ that satisfies (S). The loser is not active and not a violation. The only node whose last-child status changes, other than the loser, is the old last child of the winner, and the code pushes it on $W$.

Proof. Say $a.key \le b.key$. Then $b$ becomes the child of slot $k$ of $a$, and $a$ has the children of the ranks $0, \ldots, k$. The code removes the mark of $b$, and $b.key \ge a.key$. The children of $b$ keep their parent. The old child of rank $k - 1$ of $a$ was the last child and is not any more; the code pushes it. The rank of $a$ changes, and the code moves $a$ in the table of active nodes if $a$ is active. $\square$

Lemma 2 (shape). Every operation keeps (S), and every rank is at most $\lfloor \lg n \rfloor$.

Proof. Look at each change of the trees. INSERT and the carries of delete-min only link roots of equal rank (Lemma 1) and put the result in the root table, carrying while the rank is taken, as in a binary counter. PARENT$(s)$: $s$ is the last child of $p$, so $r(s) = r(p) - 1$. After the cut $r(p) = r(s)$, so the link of $p$ under $s$ gives $s$ the rank $r(s) + 1$, which is the old rank of $p$, and $s$ goes to the slot of $p$. TRIPLE$(v, s, c)$: $v$ and $c$ have rank $r$, and $s$ has rank $r + 1$; after the cut $s$ has rank $r$ and goes to slot $r$, and LINK$(v, c)$ has rank $r + 1$ and goes to slot $r + 1$. CLEAN exchanges two nodes of rank $r$. PAIR$(x, y)$: $p$ and $q$ have rank $r + 1$, since $x$ and $y$ are their last children of rank $r$; after the cuts both have rank $r$, $q$ goes to slot $r$ of $p$, and LINK$(x, y)$ of rank $r + 1$ goes to the old slot of $q$. The parents differ, and neither of $p$ and $q$ is a descendant of the other, because a subtree of a node of rank $r + 1$ holds only nodes of smaller rank below its root. So no cycle forms. In DELETE-MIN, if $m$ of rank $r$ is not a root after line L13, then $t$ has rank 0, and the links with the children of $m$ of the ranks $0, 1, \ldots, r - 1$, in this order, give ranks $1, 2, \ldots, r$; the result fills slot $r$ of the parent of $m$. If $m$ is a root, its children become roots. So the shape is always binomial. A binomial tree of rank $k$ has $2^k$ nodes by induction ($2^k = 1 + \sum_{i < k} 2^i$), so $2^k \le n$. Every move to the root table or a call of PLACE with no parent removes the mark, so roots are not active. Every change of the rank of a node goes through the helper that moves the node in the table of active nodes. $\square$

Lemma 3 (heap order of the moves). No transformation and no link makes a node a violation, except the nodes that it pushes on $W$.

Proof. We list the nodes that get a new parent or a new key. LINK: the loser is not a violation (Lemma 1). PARENT$(s)$ with $s.key < p.key$: $p$ goes under $s$, and $p.key > s.key$; $s$ gets the parent of $p$ and is pushed. TRIPLE: the condition of line L8 is false when line L9 runs, because either it was false for the first $s$, or PARENT ran; in the second case PARENT either makes $v$ the last child of $p$ (when $s$ moves up, $p$ loses its last child $s$ and $v$ becomes the last child), or puts $s$ back with $s.key \ge p.key$. So $s.key \ge p.key$, and $s$ in the slot of $v$ is not a violation; it is pushed anyway. The tree LINK$(v, c)$ gets the parent $p$ and is pushed. CLEAN: $c$ is not active and $c.key \ge s.key \ge p.key$, so $c$ under $p$ is not a violation; $v$ under $s$ is pushed. PAIR: $q$ under $p$ has $q.key \ge p.key$; LINK$(x, y)$ in the old place of $q$ is pushed. DELETE-MIN: the children of $m$ are linked under $t$ or under each other as losers, and the result is pushed. A decrease of the key of $x$ keeps the children of $x$ in order, and $x$ itself is pushed at line L4. $\square$

Lemma 4 (the work list). At the top of the loop of FIX the following hold: (W1) every non-root node that is a violation and not active is on $W$; (W2) every active node that is not a last child is on $W$; (W3) for each rank $r$, at most one active node of rank $r$ is not on $W$. When $W$ is empty, (a), (b) and (c) hold.

Proof. When an operation calls FIX, (a), (b) and (c) held before the operation. The operation changes parents, slots, or the key of $x$, and by Lemmas 1 and 3 it pushes every node whose parent, key or last-child status changed and that can be a violation or active. Line L13 makes children of $t$ roots, and roots satisfy all three properties. So (W1) to (W3) hold at the first test.

Now take one pass of the loop with the node $v$. The nodes that the pass changes are $v$, the nodes that a transformation moves, and the nodes whose last-child status changes; by Lemmas 1 and 3 all these are pushed, except the losers of links and the nodes put in place without a violation, and these are not active and not violations. So (W1) and (W2) can fail only for $v$ itself. Line L5: $v$ is a root or not a violation, and it becomes not active, so it breaks nothing. Lines L8 to L10 end the pass with $v$ pushed again (lines L8 and L10) or with $v$ not active, inside the pushed tree LINK$(v, c)$ (line L9), except when PARENT makes $v$ the last child; then the pass goes on to line L11 with $v$ active and a last child. At line L11, $v$ is an active last child. If no other active node has rank $r$, then $v$ is the only active node of rank $r$ off $W$, so (W3) holds. If another active node $y$ of rank $r$ exists and line L11 pushes $v$ and $y$, then (W3) holds since $v$ is on $W$. If PAIR runs, the marks of $v$ and $y$ go away, and by (W3) before the pass, at most one active node of rank $r$ was off $W$ other than $v$; after the pass that is still true. A change of the rank of an active node happens only to a node that the same step pushes (the node $s$ of TRIPLE, the nodes $p$ of PARENT and PAIR, which lose their mark or get their old rank back), so it cannot break (W3).

If $W$ is empty, (W1) gives (c), (W2) gives (b), and (W3) gives (a). $\square$

Lemma 5 (termination). FIX ends.

Proof. Let $V$ be the set of violations and define $M = (|V|, -\sum_{v \in V} r(v), N, Z)$, where $N$ is the number of violations that are not last children and $Z$ is the number of stale marks. Every component is a bounded integer, since $|V| \le n$ and all ranks are at most $\lg n$. Keys do not change in FIX, and a node changes its parent only in a transformation or a link. We show that each transformation lowers $M$ in lexicographic order.

• PAIR: $x$ and $y$ are violations before. After, $q$ is under $p$ and not a violation, the loser of LINK$(x, y)$ is not a violation, and only the winner can be one. If $q$ was a violation, it is replaced by the winner. So $|V|$ drops by at least 1.
• TRIPLE: $v$ is a violation. If $c$ is a violation too, the two are replaced by at most the winner, so $|V|$ drops. If $c$ has a stale mark, either the winner is not a violation and $|V|$ drops, or $v$ of rank $r$ is replaced in $V$ by the winner of rank $r + 1$, so the second component drops. The node $s$ is not a violation before or after.
• PARENT$(s)$ with $s.key < p.key$: $s$ is a violation before, and $p$ under $s$ is not after. If $p$ was a violation, $|V|$ drops. Otherwise either $s$ is not a violation in the place of $p$, and $|V|$ drops, or $s$ stays in $V$ with the rank of $p$, which is one larger, and the second component drops.
• CLEAN: $v$ is a violation before and after, with the same rank; $c$ is not a violation before or after. $v$ was not a last child and now is, and no other node changes its last-child status in a way that matters: $c$ is not a violation. So $N$ drops. Line L5 removes a mark from a node that is not a violation, or does nothing, so $Z$ drops or $M$ stays. Line L6 marks a violation, so $Z$ does not change. So $M$ never grows in FIX, and it drops at each transformation. So there are finitely many transformations.

Between two transformations, $M$ does not grow, and passes that do not change $M$ are of three kinds: a pop that ends at line L5 with no change, a pop that ends at line L11 with nothing to do, and a pass that pushes two nodes at line L8 or line L11. A push at line L8 puts a violation $s$ of rank $r + 1$ that is not a last child on top of $W$. The next pass handles $s$: it reaches line L7, and either a transformation runs or line L8 pushes a node of rank $r + 2$. So a chain of such pushes has length at most $\lg n$ and ends with a transformation. A push at line L11 puts $y$ on top. The next pass handles $y$: either $y$ is not a violation, and line L5 removes its mark, which lowers $Z$; or $y$ is a violation that is not a last child, and then a chain as above ends with a transformation. So between two drops of $M$ there are at most $O(\log n)$ pushes, and so $O(\log n) + |W|$ passes. Since $M$ drops finitely often, FIX ends. $\square$

Lemma 6 (find-min). When (c) holds, the smallest key is the key of a root or of an active node.

Proof. Take a node $x$ of smallest key. While the current node is not a root and not active, go to its parent; by (c) the key of the parent is at most the key of the node. The walk ends at a root or an active node, whose key is at most $x.key$, so it is also a smallest key. $\square$

Theorem. After each operation, the heap holds exactly the inserted keys that were not deleted, with their current values, and (S), (a), (b), (c) hold; FIND-MIN and DELETE-MIN return a smallest key.

Proof. Lemma 2 gives (S), Lemma 5 that FIX ends, and Lemma 4 that (a), (b) and (c) hold when it ends. Insert adds one node. Decrease-key changes one key. Transformations and links only move nodes. In DELETE-MIN the node $m$ is removed from the trees: if $m$ is not a root, it is not in the tree of rank $r$ that fills its slot, and $t$ is in that tree; if $m$ becomes a root, it is removed from the root table and $t$ is added back. So exactly $m$ leaves, and $m$ has a smallest key by Lemma 6, applied to the state before the operation, when (c) held. The returned key was saved before the change. $\blacksquare$