Proofs: Kinetic heap

The kinetic heap reports the minimum at every time, and processes exactly Φ events in the worst case full

This proof shows: correctness.

We use the definitions of the page. Each item $e$ has the key $k_e(t) = a_e + b_e t$. The order just after time $s$ is: $e \prec_s f$ if $k_e(s) < k_f(s)$, or $k_e(s) = k_f(s)$ and $b_e < b_f$. Write $e \preceq_s f$ if $e \prec_s f$ or the two keys and slopes are equal. The invariants at the end of each operation are (I1) $H[parent(i)] \preceq_{now} H[i]$ for every $i > 0$; (I2) every position $i > 0$ has a current certificate whose failure time is $fail(i)$ as defined on the page, and every finite one is larger than $now$.

Lemma 1 (a certificate). Let $p$ and $c$ be two items with $p \preceq_s c$. If $b_p \le b_c$, then $k_p(t) \le k_c(t)$ for all $t \ge s$. If $b_p > b_c$, let $\tau = (a_c - a_p)/(b_p - b_c)$; then $\tau \ge s$, $k_p(t) \le k_c(t)$ exactly for $t \le \tau$, and $c \prec_\tau p$.

Proof. The difference $d(t) = k_c(t) - k_p(t) = (a_c - a_p) + (b_c - b_p) t$ is linear, and $d(s) \ge 0$. If $b_c \ge b_p$, it does not decrease, so $d(t) \ge 0$ for $t \ge s$. If $b_c < b_p$, it decreases and has its only zero at $\tau$. Since $d(s) \ge 0$, $\tau \ge s$, and $d(t) \ge 0$ exactly when $t \le \tau$. At $\tau$ the keys are equal and $b_c < b_p$, so $c \prec_\tau p$. $\square$

Lemma 2 (between events). If (I1) and (I2) hold at time $now$ and no finite failure time is in $[now, t]$, then $H[0]$ has a smallest key at every time in $[now, t]$, and (I1) and (I2) hold at time $t$.

Proof. By Lemma 1, for each edge either the certificate never fails, or it fails after $t$; in both cases the parent key is at most the child key at all times in $[now, t]$. Then by induction on the depth, $k_{H[0]}(s) \le k_{H[i]}(s)$ for all $i$ and all such $s$. For (I1) at time $t$: if $b_p \le b_c$, the keys at $t$ are in order and, if equal, the slopes are in order. If $b_p > b_c$, the failure time is larger than $t$, so $k_p(t) < k_c(t)$. The certificates depend only on the items at the positions, which do not change, so (I2) holds, with all finite failure times larger than $t$. $\square$

Lemma 3 (an event). Suppose that before line L5 the heap satisfies $H[parent(j)] \preceq_\tau H[j]$ for every edge except possibly the edges whose certificates have failure time $\tau$, and every such edge has $c \prec_\tau p$ with equal keys. Process one of them at position $i$. Afterwards the same statement holds, with one edge less of this kind or with new ones only of the same kind, and every certificate is correct.

Proof. Let $p$ be the item at $q = parent(i)$ and $c$ the item at $i$; by Lemma 1, $k_p(\tau) = k_c(\tau)$ and $b_c < b_p$. After the swap, $c$ is at $q$ and $p$ at $i$, and $c \prec_\tau p$, so the edge from $q$ to $i$ is in order, and its certificate never fails. The edges that changed their items are those at $q$ and at $i$; line L6 computes their certificates again. The edge from $q$ to its other child $w$: before, $p \preceq_\tau w$ or the edge was a failing one; now $c$ is the parent, with $k_c(\tau) = k_p(\tau)$ and $b_c < b_p$, so if $p \preceq_\tau w$ then $c \prec_\tau w$. The edges from $i$ to its children $x$: before, $c \preceq_\tau x$ or a failing edge; now $p$ is the parent, and the new certificate is computed by line L6; if $x \prec_\tau p$, the edge has failure time $\tau$ by the formula (the keys of $p$ and $c$ are equal at $\tau$, so $k_x(\tau) \ge k_p(\tau)$, and $x \prec_\tau p$ means equality and $b_x < b_p$). The edge above $q$: the parent $g$ had $g \preceq_\tau p$; now the child is $c$, with the same key as $p$ at $\tau$; if $c \prec_\tau g$, then the keys are equal and the slope of $c$ is smaller, so the failure time is $\tau$. In all cases an edge is either in order just after $\tau$, or has failure time $\tau$ with equal keys, as claimed. $\square$

Lemma 4 (the potential). Let $\Phi'$ be the number of pairs of items $(f, g)$ such that $f$ is at a proper ancestor of the position of $g$ and $b_g < b_f$. Each event lowers $\Phi'$ by at least 1. So, if no item is inserted or deleted, ADVANCE processes at most $\Phi'$ events, and this is at most $\Phi = \sum_i depth(i)$.

Proof. This is Lemma 2 of da Fonseca and de Figueiredo, written for a min-heap. Let the event swap $p$ at $q$ and $c$ at $i$, with $b_c < b_p$. Let $w$ be the other child of $q$. Split the other items into three sets. For an item that is not in the subtree of $q$, its set of descendants is the same set of items before and after, and so is its set of ancestors. For an item in the subtree of $i$ below $i$, its ancestors are the same set of items: $p$ and $c$ just exchange places. For an item $x$ in the subtree of $w$, the ancestor $p$ is replaced by $c$; the pair counts after only if $b_x < b_c$, which implies $b_x < b_p$, so the count for $x$ does not grow. The pairs with $p$ or $c$ as the descendant: the ancestors of $q$ are ancestors of both before and after. The pairs with $p$ or $c$ as the ancestor are covered by the cases above, except the pair of $p$ and $c$ itself: before, $p$ is above $c$ and $b_c < b_p$, so it counts; after, $c$ is above $p$ and $b_p < b_c$ is false, so it does not. So $\Phi'$ drops by at least 1. It is never negative, so the number of events is at most its initial value. Each item at depth $d$ is in at most $d$ pairs as the descendant, so $\Phi' \le \Phi$. $\square$

Lemma 5 (the lower bound). For $k_s(t) = -2 s t + s^2$, $s = 0, 1, \ldots, n - 1$, and a start time $t_0 < -n$, ADVANCE to $t_1 > 2n$ processes exactly $\Phi$ events.

Proof. $k_s(t) + t^2 = (t - s)^2$, so at time $t$ the item with the smallest key is the one with $s$ nearest to $t$. At $t = s$ this is the item $s$ alone, so every item is at the root at some time in $[t_0, t_1]$. An event moves one item up by one level and one item down. So an item that starts at depth $d$ needs at least $d$ events in which it moves up, and these are different events for different items. So there are at least $\Phi$ events, and by Lemma 4 at most $\Phi$. $\square$

Theorem. After each operation, (I1) and (I2) hold, and FIND-MIN returns an item with the smallest key at time $now$. With no inserts and deletes, the number of events is at most $\Phi \le n \lfloor \lg n \rfloor$, and this is tight.

Proof. INSERT and DELETE are the usual sift operations of a binary heap under the order $\prec_{now}$, so (I1) holds after them, and lines L10 and L12 compute the certificate of every edge whose items changed; by Lemma 1 every finite failure time is at least $now$, and it equals $now$ only if the child is before the parent in $\prec_{now}$, which (I1) excludes. So (I2) holds. In ADVANCE, the loop takes the earliest failure time $\tau$. By Lemma 2 the heap is valid up to $\tau$. By Lemma 3, after the events at time $\tau$ that the loop processes, every edge is in order just after $\tau$ or has failure time $\tau$; the loop goes on while there is one with failure time $\tau \le t$, and by Lemma 4 the number of events is finite, so the loop leaves time $\tau$ with (I1) and (I2) at $\tau$. Then Lemma 2 applies again up to the next failure time or $t$. When the loop ends, Lemma 2 gives (I1) and (I2) at $t$, and by (I1) and induction on depth, $H[0]$ has a smallest key at $now$. The bound on the events is Lemma 4 and its tightness is Lemma 5; the depth of each of the $n$ positions is at most $\lfloor \lg n \rfloor$. $\blacksquare$