5 \chapter{Approaching Optimality}
9 Recently, Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann}
10 have presented algorithms for the MST with worst-case time complexity
11 $\O(m\timesalpha(m,n))$ on the Pointer machine. We will devote this chapter to their results
12 and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal},
13 which is provably optimal.
15 At the very heart of all these algorithms lies the \df{soft heap} discovered by
16 Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly
17 similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
18 and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
19 the expense of \df{corrupting} a~fraction of the inserted elements by raising
20 their values (the values are however never lowered). This allows for
21 an~trade-off between accuracy and speed controlled by a~parameter~$\varepsilon$.
22 The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every
23 moment at most~$\varepsilon n$ elements of the~$n$ elements inserted can be
26 \defnn{Soft heap operations}%
27 The soft heap contains a~set of distinct items from a~totally ordered universe and it
28 supports the following operations:
30 \:$\<Create>(\varepsilon)$ --- create an~empty soft heap with the given accuracy parameter~$\varepsilon$,
31 \:$\<Insert>(H,x)$ --- insert a~new element~$x$ to the heap~$H$,
32 \:$\<Meld>(P,Q)$ --- merge two heaps into one, more precisely move all elements of a~heap~$Q$
33 to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$),
34 \:$\<DeleteMin>(H)$ --- delete the minimum element of the heap~$H$ and return its value
35 (optionally signalling that the value has been corrupted).
38 \examplen{Linear-time selection}
39 We can use soft heaps to select the median (or generally the $k$-th smallest element)
40 of a~sequence. We insert all $n$~elements to a~soft heap with error rate $\varepsilon=1/3$.
41 Then we delete the minimum about $n/3$ times and we remember the current (possibly corrupted)
42 value~$x$ of the last element deleted. This~$x$ is greater or equal than the current
43 values of the previously deleted elements and thus also than their correct values.
44 On the other hand, the current values of the $2n/3$ elements remaining in the heap
45 are greater than~$x$ and at most $n/3$ of them are corrupted. Therefore at least $n/3$
46 elements are greater than~$x$ and at least $n/3$ ones are smaller. Depending on the value
47 of~$k$, we can always throw away one of these parts and recurse on the rest (similarly to
48 the Hoare's Quickselect algorithm \cite{hoare:qselect}). The total time complexity will
49 be $\O(n+(2/3)\cdot n+(2/3)^2\cdot n+\ldots) = \O(n)$. We have obtained a~nice alternative to the standard
50 linear-time selection algorithm by Blum \cite{blum:selection}. The same trick can be used
51 to select a~good pivot in Quicksort \cite{hoare:qsort}, leading to time complexity $\O(n\log n)$
55 The soft heap is built from \df{soft queues} (we will usually omit the adjective soft
56 in the rest of this section). Each queue has a~shape of a~binary tree.\foot{%
57 Actually, Chazelle defines the queues as binomial trees, but he transforms them in ways that are
58 somewhat counter-intuitive, albeit well-defined. We prefer describing the queues as binary
59 trees with a~special distribution of values. In fact, the original C~code in the Chazelle's
60 paper \cite{chazelle:softheap} uses this representation internally.}
61 Each vertex~$v$ of the tree remembers a~doubly-linked list of items. The
62 item list in every left son will be used only temporarily and it will be kept
63 empty between operations. Only right sons and the root have their lists
64 permanently occupied. The left sons will be called \df{white}, the right ones
65 \df{black.} (See the picture.)
67 The first value in every list is called the \df{controlling key} of the vertex,
68 denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used
69 value or we set $\<ckey>(v)=+\infty$. The \<ckey> obey the standard \df{heap order}
70 --- a~\<ckey> of a~parent is always smaller than the \<ckey>'s of its sons.
72 Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
73 The ranks of leaves are always zero, the rank of every internal vertex can be
74 arbitrary, but it must be strictly greater than the ranks of its sons. We
75 define the rank of the whole queue to be equal to the rank of its root vertex and
76 similarly for its \<ckey>.
78 A~queue is called \df{complete} if every two vertices joined by an~edge have rank
79 difference exactly one. In other words, it is a~complete binary tree and the
80 ranks correspond to vertex heights.
82 \figure{softheap1.eps}{\epsfxsize}{\multicap{A~complete and a~partial soft queue tree\\
83 (black vertices contain items, numbers indicate ranks)}}
86 The complete queue of rank~$k$ contains exactly~$2^{k+1}-1$ vertices, $2^k$~of which are
87 black (by induction). Any other queue can be trivially embedded to the complete queue of the same
88 rank, which we will call the \df{master tree} of the queue. This embedding preserves vertex
89 ranks, colors and the ancestor relation.
91 The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
92 two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
93 of the original roots and also its \<ckey>. To preserve the heap order, we will choose
94 the one whose \<ckey> is smaller.
96 Sometimes, we will also need to split a~queue to smaller queues. We will call this operation
97 \df{dismantling} the queue and it will happen only in cases when the item list in the root
98 is empty. It suffices to remove the leftmost (all white) path going from the root. From
99 a~queue of rank~$k$, we get queues of ranks $0,1,\ldots,k-1$, some of which may be missing
100 if the original queue was not complete.
102 \figure{softheap2.eps}{\epsfxsize}{Joining and dismantling of soft queues}
104 We will now define the real soft heap and the operations on it.
106 \defn A~\df{soft heap} consists of:
108 \:a~doubly linked list of soft queues of distinct ranks (in increasing order of ranks),
109 we will call the first queue the \df{head} of the list, the last queue will be its \df{tail};
110 \:\df{suffix minima:} each queue contains a~pointer to the queue with minimum \<ckey>
111 of those following it in the list;
112 \:a~global parameter~$r$: an~even integer to be set depending on~$\varepsilon$.
115 \>We will define the \df{rank} of a~heap as the highest of the ranks of its queues
116 (that is, the rank of the heap's tail).
118 The heap always keeps the \df{Rank invariant:} When a~root of any tree has rank~$k$,
119 its leftmost path contains at least~$k/2$ vertices.
121 \paran{Operations on soft heaps}
123 \em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble
124 the heap of the smaller rank and we insert its queues to the other heap.
125 If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
126 a~single queue of rank~$k+1$ as already described and we propagate the new queue as
127 a~\df{carry} to the next iteration, similarly to addition of binary numbers.
128 Finally we have to update the suffix minima by walking the new list backwards
129 from the last inserted item.
131 \em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating
132 a~single-element heap and melding it to the destination heap.
134 \algn{Creating a~new soft heap}
136 \algin The~parameter~$\varepsilon$ (the accuracy of the heap).
137 \:Allocate memory for a~new heap structure~$H$.
138 \:Initialize the list of queues in~$H$ to an~empty list.
139 \:Set the parameter~$r$ to~$2\lceil\log(1/\varepsilon)\rceil+2$ (to be justified later).
140 \algout A~newly minted soft heap~$H$.
143 \algn{Melding of two soft heaps}
145 \algin Two soft heaps~$P$ and~$Q$.
146 \:If $\<rank>(P) < \<rank>(Q)$, exchange the item lists of~$P$ and~$Q$.
148 \brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that
149 there is an~empty queue of infinite rank there.}
150 \:While $Q$ still has some queues:
152 \::If $\<rank>(p) < \<rank>(q)$, then $p\=$ the successor of~$p$,
153 \::else if $\<rank>(p) > \<rank>(q)$, remove~$q$ from~$Q$ and insert it to~$P$ before~$p$,
154 \::otherwise (the ranks are equal, we need to propagate the carry):
156 \:::Remove~$p$ from~$P$ and set $p\=$ the original successor of~$p$.
157 \:::While $\<rank>(q)=\<rank>(\<carry>)$:
158 \::::Remove~$q$ from~$Q$.
159 \::::$\<carry>\=\<join>(q, \<carry>)$.
160 \::::$q\=\<head>(Q)$.
161 \:::Insert~\<carry> before~$q$.
162 \:Update the suffix minima: Walk with~$p$ backwards to the head of~$P$:
163 \::$p'\=\<suffix\_min>$ of the successor of~$p$.
164 \::If $\<ckey>(p) < \<ckey>(p')$, set $\<suffix\_min>(p)\=p$.
165 \::Otherwise set $\<suffix\_min>(p)\=p'$.
166 \:Destroy the heap~$Q$.
167 \algout The merged heap~$P$.
170 \algn{Insertion of an~element to a~soft heap}
172 \algin A~heap~$H$ and a~new element~$x$.
173 \:Create a~new heap~$H'$ of the same parameters as~$H$. Let~$H'$ contain a~sole queue of rank~0,
174 whose only vertex has the element~$x$ in its item list.
176 \algout An~updated heap~$H$.
180 So far, the mechanics of the soft heaps were almost identical to the binomial heaps
181 and the reader could rightfully yawn. The things are going to get interesting
182 now as we approach the parts where corruption of items takes place.
184 If all item lists contain at most one item equal to the \<ckey> of the particular
185 vertex, no information is lost and the heap order guarantees that the minimum item
186 of every queue stays in its root. We can however allow longer lists and let the items
187 stored in a~single list travel together between the vertices of the tree, still
188 represented by a~common \<ckey>. This data-structural analogue of car pooling will
189 allow the items to travel at a~faster rate, but as only a~single item can be equal
190 to the \<ckey>, all other items will be inevitably corrupted.
192 We of course have to be careful about the size of the lists, because we must avoid corrupting
193 too many items. We will control the growth according to the vertex ranks. Vertices
194 with rank at most~$r$ will always contain just a~single item. Above this level,
195 the higher is the rank, the longer list will be allowed.
198 \em{Deletion of minimum} will be based on this principle. The minimum is easy to locate
199 --- we follow the \<suffix\_min> of the head of the heap to the queue with the minimum
200 \<ckey>. There we look inside the item list of the root of the queue. We remove the \em{last}
201 item from the list (we do not want the \<ckey> to change) and we return it as the minimum.
202 (It is not necessarily the real minimum of all items, but always the minimum of their
203 possibly corrupted values.)
205 If the list becomes empty, we \em{refill} it with items from the lower levels of the
206 same queue. This process can be best described recursively: We ask the left son to refill itself
207 (remember that the left son is always white, so there are currently no items there). If the new
208 \<ckey> of the left son is smaller than of the right son, we immediately move the left
209 son's list to its parent. Otherwise, we exchange the sons and move the list from the
210 new left son to the parent. This way we obey the heap order and at the same time we keep
211 the white left son free of items.
213 Ocassionally, we repeat this process once again and we concatenate the resulting lists
214 (we append the latter list to the former, using the smaller of the two \<ckey>'s). This
215 makes the lists grow longer and we want to do that roughly on every other level of the
216 tree. The exact condition will be that either the rank of the current vertex is odd,
217 or the difference in ranks between this vertex and its right son is at least two.
219 If refilling of the left son fails because there are no more items in that subtree
220 (we report this by setting its \<ckey> to $+\infty$), the current vertex is no longer
221 needed --- the items would just pass through it unmodified. We therefore want to
222 remove it. Instead of deleting it directly, we rather make it point to its former
223 grandsons and we remove the (now orhpaned) original son. This helps us to ensure
224 that both sons always keep the same rank, which will be useful for the analysis.
226 When all refilling is done, we update the suffix minima by walking from the current
227 queue to the head of the heap exactly as we did in the \<Meld> procedure.
229 Our only remaining worry is that the Rank invariant can be broken after the
230 refilling. When the leftmost path of the tree becomes too short, we just
231 \em{dismantle} the tree as already described and we meld the new trees back to
232 the heap. This is easier to handle when the item list at the root vertex is
233 empty. We will therefore move this check before the refilling of the root list.
234 It will turn out that we have enough time to always walk the leftmost path
235 completely, so no explicit counters are needed.
237 Let us translate these ideas to real (pseudo)code:
239 \algn{Deleting the minimum item from a~soft heap}
241 \algin A~soft heap~$H$.
242 \:Use \<suffix\_min> of the head queue of~$H$ to locate the queue~$q$ with the smallest \<ckey>.
243 \:Remove the final element~$x$ of the item list in the root of~$q$.
244 \:If the item list is empty:
245 \::Count the vertices on the leftmost path of~$q$.
246 \::If there are less than $\<rank>(q)$ of them:
247 \:::Remove~$q$ from the list of queues.
248 \:::Recalculate the suffix minima as in the \<Meld> procedure.
249 \:::Dismantle~$q$ and create a~heap~$H'$ holding the resulting trees.
250 \:::Meld them back: $\<Meld>(H,H')$.
252 \:::Call \<Refill> on the root of~$q$.
253 \:::If $\<ckey>(q)=+\infty$ (no items left), remove the tree~$q$ from~$H$.
254 \:::Recalculate the suffix minima.
255 \algout The deleted minimum item~$x$ (possibly corrupted).
258 \algn{Refilling the item list of a~vertex}
260 \algin A~soft queue and its vertex~$v$ with an~empty item list.
261 \:Handle trivial cases: If~$v$ has no children or both have $\<ckey>=+\infty$,
262 set $\<ckey>(v)$ to~$+\infty$ and return.
263 \:Let \<left> and~\<right> denote the respective sons of~$v$.
264 \:Recurse: call $\<Refill>(\<left>)$.
265 \:If $\<ckey>(\<left>) > \<ckey>(\<right>)$, swap the sons.
266 \:Move the item list from \<left> to~$v$ (implying $\<ckey>(v)=\<ckey>(\<left>)$).
267 \:If $\<rank>(v) > r$ and either $\<rank>(v)$ is odd or $\<rank>(v) > \<rank>(\<right>)+1$, recurse once more:
268 \::Repeat steps 3--4.
269 \::Append the item list from \<left> to the item list at~$v$.
270 \:Clean up. If $\<ckey>(\<right>) = +\infty$:
271 \::If $\<ckey>(\<left>) = +\infty$, unlink and discard both sons.
272 \::Otherwise relink the sons of \<left> to~$v$ and discard \<left>.
273 \algout A~modified soft queue.
276 \paran{Analysis of accuracy}
277 The description of the operations is now complete, so let us analyse their behavior
278 and verify that we have delivered what we promised --- first the accuracy of
279 the structure, then the time complexity of operations. In the whole analysis,
280 we will denote the total number of elements inserted during the history of the
281 structure by~$n$. We will also frequently take advantage of knowing that the
282 threshold~$r$ is even.
284 We start by bounding the sizes of the item lists.
287 For every vertex~$v$ of a~soft queue, the size $\ell(v)$ of its item list
289 $$\ell(v) \le \max(1, 2^{\lceil \<rank>(v)/2 \rceil - r/2}).$$
292 Initially, all item lists contain at most one item, so the ineqality trivially
293 holds. Let us continue by induction. Melds can affect it only in the favorable
294 direction (they ocassionally move an~item list to a~vertex of a~higher rank)
295 and so do deletes (they only remove items from lists). The only potentially
296 dangerous place is the \<Refill> procedure.
298 Refilling sometimes just moves items upwards, which is safe, and sometimes it
299 joins two lists into one, which generally is not. When $\<rank>(v) \le r$,
300 no joining takes place and~$\ell(v)$ is still~1. Otherwise we join when either
301 $\<rank>(v)$ is odd or $\<rank>(w) < \<rank>(v)-1$ for any son~$w$ of~$v$ (remember
302 that both sons have the same rank). In both cases, $\lceil\<rank>(w)/2\rceil \le
303 \lceil\<rank>(v)/2\rceil - 1$. By the induction hypothesis, the size of each
304 of the two joined lists is at most $2^{\max(1,\lceil\<rank>(v)/2\rceil - 1 - r/2)}$,
305 so the new list has at most $2^{\lceil\<rank>(v)/2\rceil - r/2}$ items. (The maximum
306 has disappeared since $\<rank>(v)>r$ and therefore the desired bound is at least~2.)
309 We will now sum the sizes of the lists over all vertices containing corrupted items.
311 \lemma\id{shcorrlemma}%
312 At any given time, the heap contains at most~$n/2^{r-2}$ corrupted items.
315 We first prove an~auxiliary claim: The master trees of all queues contain at most~$n$
316 black vertices. This follows by induction: If no deletions have taken place,
317 there are exactly~$n$ black vertices, because insertion adds one black vertex and
318 melding preserves their number. A~deletion affects the master trees only when
319 dismantling takes place and then it only removes a~black vertex.
321 An~obvious upper bound on the number of corrupted items is the total size of item
322 lists in all vertices of rank greater than~$r$. We already know from the previous
323 lemma that the list sizes are limited by a~function of the ranks. A~complete tree
324 is obviously the worst case, so we will prove that this lemma holds for the master
325 tree of every queue in the heap. The actual trees can be much sparser, but the
326 above claim guarantees that the total size of the master trees is bounded by the
327 number of insertions properly.
329 So let us consider a~complete tree of~rank~$k$. It has exactly $2^{k-i}$ vertices
330 of rank~$i$ and each such vertex contains a~list of at most~$2^{\lceil i/2\rceil - r/2}$
331 items by the previous lemma. Summing over all ranks greater than~$r$, we get that
332 the total number of corrupted items in this tree is at most:
334 \sum_{i=r+1}^k 2^{k-i}\cdot 2^{\lceil i/2\rceil - r/2}
335 = 2^{k-r/2} \cdot \sum_{i=r+1}^k 2^{\lceil i/2\rceil - i}
336 \le 2^{k-r/2+1/2} \cdot \sum_{i=r+1}^k 2^{-i/2}
337 \le 2^{k-r} \cdot \sum_{i=0}^\infty 2^{-i/2}.
339 The sum of a~geometric series with quotient $2^{-1/2}$ is less than four, so the
340 last expression is less than $2^{k-r+2}$. Since the tree contains $n_k=2^k$ black vertices,
341 this makes less than $n_k/2^{r-2}$ corrupted items as we asserted.
344 \paran{Analysis of time complexity}
345 Now we will examine the amortized time complexity of the individual operations.
346 We will show that if we charge $\O(r)$ time against every element inserted, it is enough
347 to cover the cost of all other operations.
349 All heap operations use only pointer operations, so it will be easy to derive the time
350 bound in the Pointer machine model. The notable exception is however that the procedures
351 often refer to the ranks, which are integers on the order of $\log n$, so they cannot
352 fit in a~single memory cell. For the time being, we will assume that the ranks can
353 be manipulated in constant time, postponing the proof for later.
355 We take a~look at the melds first.
358 The amortized cost of a~meld is $\O(1)$, except for melds induced by dismantling
359 which take $\O(\<rank>(q))$, where $q$~is the queue to be dismantled.
362 The real cost of a~meld of heaps $P$ and~$Q$ is linear in the smaller of
363 their ranks, plus the time spent on carry propagation. The latter is easy to
364 dispose of: Every time there is a~carry, the total number of trees in all
365 heaps decreases by one. So it suffices to charge $\O(1)$ against creation of
366 a~tree. An~insert creates one tree, dismantling creates at most $\<rank>(q)$
367 trees, and all other operations alter only the internal structure of trees.
369 As for the $\O(\min(\<rank>(P),\<rank>(Q)))$ part, let us assume for a~while that
370 no dismantling ever takes place and consider the \df{meld forest.} It is a~forest
371 whose leaves correspond to the $n$~single-element heaps constructed by \<Insert>
372 and each internal vertex represents a~heap arisen from melding its sons. The left
373 son will be the one with the greater or equal rank. We therefore want to bound
374 the sum of ranks of all right sons.
376 For every right son, we will distribute the change for its rank~$k$ among all leaves
377 in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the same
378 rank twice, because the ranks of right sons on every path from the root of the
379 tree to a~leaf are strictly decreasing. (This holds because melding of two heaps
380 always produces a~heap of a~strictly greater rank.) Hence at most~$n/2^k$
381 right sons have rank~$k$ and the total time charged against the leaves is bounded by:
383 \sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = 2n.
386 Let us return dismantling to the game. When a~queue is dismantled, melding the parts
387 back to the heap takes $\O(\<rank>(q))$ time. We can therefore let the dismantling pay for it
388 and omit such induced melds from the meld forest. As the rank of a~heap is never increased
389 by induced melds, the above calculation is still a~proper upper bound on the cost
390 of the regular melds.
393 Before we estimate the time spent on deletions, we analyse the refills.
396 Every invokation of the \<Refill> procedure takes time $\O(1)$ amortized.
399 When \<Refill> is called from the \<DeleteMin> operation, it recurses on a~subtree of the
400 queue. This subtree can be split to the ``lossless'' lower part (rank~$r$ and below)
401 and the upper part where list concatenation and thus also corruption takes place. Whenever
402 we visit the lower part during the recursion, we spend at worst $\O(r)$ time there.
403 We will prove that the total time spent in the upper parts during the whole life of the
404 data structure is $\O(n)$. Since each upper vertex can perform at most two calls to the lower
405 part, the total time spent in the lower parts is $\O(rn)$. All this can be prepaid by the
408 Let us focus on the upper part. There are three possibilities of what can happen
409 when we visit a~vertex:
413 \:We delete it: Every vertex deleted has to have been created at some time in the past.
414 New vertices are created only during inserts and melds (when joining two trees) and
415 we have already shown that these operations have constant amortized complexity. Then the
416 same must hold for deletions.
418 \:We recurse twice and concatenate the lists: The lists are disassembled only when
419 they reach the root of the tree, otherwise they are only concatenated. We can easily
420 model the situation by a~binary tree forest similar to the meld forest. There are~$n$
421 leaves and every internal vertex has outdegree two, so the total number of concatenations
422 is at most~$n$. Each of them can be performed in constant time as the list is doubly linked.
424 \:We recurse only once: This occurs only if the rank is even and the gap between the
425 rank of this vertex and its sons is equal to~1. It therefore cannot happen twice in a~row,
426 thus it is clearly dominated by the cost of the other possibilities.
429 \>The total cost of all steps in the upper part is therefore $\O(n)$.
432 We now proceed with examining the \<DeleteMin> operation.
435 Every \<DeleteMin> takes $\O(1)$ time amortized.
438 Aside from refilling, which is $\O(1)$ by the previous lemma, the \<DeleteMin>
439 takes care of the Rank invariant. This happens by checking the length of the leftmost
440 path and dismantling the tree if the length is too far from the tree's rank~$k$.
441 When the invariant is satisfied, the leftmost path is visited by the subsequent
442 call to \<Refill>, so we can account the check on the refilling.
444 When we are dismantling, we have to pay $\O(k)$ for the operation itself and
445 another $\O(k)$ for melding the trees back to the heap. Since we have produced at most
446 $k/2$ subtrees of distinct ranks, some subtree of rank $k/2$ or more must be missing.
447 Its master tree contained at least $2^{k/2}$ vertices which are now permanently gone
448 from the data structure, so we can charge the cost against them.
449 A~single vertex can participate in the master trees of several dismantlings, but their
450 ranks are always strictly increasing. By the same argument as in the proof of
451 Lemma \ref{shmeld} (complexity of \<Meld>), each vertex pays $\O(1)$.
453 We must not forget that \<DeleteMin> also has to recalculate the suffix minima.
454 In the worst case, it requires touching $k$~trees. Because of the Rank invariant,
455 this is linear in the size of the
456 leftmost path and therefore it can be also paid for by \<Refill>. (Incidentally,
457 this was the only place where we needed the invariant.)
460 It remains to take care of the calculation with ranks:
463 Every manipulation with ranks performed by the soft heap operations can be
464 implemented on the Pointer machine in constant amortized time.
467 We create a~``yardstick'' --- a~double linked list whose elements represent the possible
468 values of a~rank. Every vertex of a~queue will store its rank as a~pointer to
469 the corresponding ``tick'' of the yardstick. We will extend the list as necessary.
471 Comparison of two ranks for equality is then trivial, as is incrementing or decrementing
472 the rank by~1. Testing whether a~rank is odd can be handled by storing an~odd/even
473 flag in every tick. This covers all uses of ranks except for the comparisons for inequality
474 when melding. In step~1 of \<Meld>, we just mark the ticks of the two ranks and walk
475 the yardstick from the beginning until we come across a~mark. Thus we compare the ranks
476 in time proportional to the smaller of them, which is the real cost of the meld anyway.
477 The comparisons in steps 5 and~6 are trickier, but since the ranks of the elements put
478 to~$P$ are strictly increasing, we can start walking the list at the rank of the previous
479 element in~$P$. The cost is then the difference between the current and the previous rank
480 and their sum telescopes, again to the real cost of the meld.
483 Now we can put the bits together and laurel our effort with the following theorem:
485 \thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}
486 A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
487 a~sequence of operations starting with an~empty heap and containing $n$~\<Insert>s
488 in time $\O(n\log(1/\varepsilon))$ on the Pointer machine. At every moment, the
489 heap contains at most $\varepsilon n$ corrupted items.
492 We set the parameter~$r$ to~$2+2\lceil\log (1/\varepsilon)\rceil$. The rest follows
493 from the analysis above. By Lemma \ref{shcorrlemma}, there are always at most $n/2^{r-2}
494 \le \varepsilon n$ corrupted items in the heap. By Lemma \ref{shmeld}--\ref{shyards},
495 the time spent on all operations in the sequence can be paid for by charging $\O(r)$ time
496 against each \<Insert>. This yields the time bound.
500 When we set $\varepsilon = 1/2n$, the soft heap is not allowed to corrupt any
501 items, so it can be used like any usual heap. By the standard lower bound on
502 sorting it therefore requires $\Omega(\log n)$ time per operation, so the
503 time complexity is optimal for this choice of~$\varepsilon$. Chazelle \cite{chazelle:softheap}
504 proves that it is optimal for every choice of~$\varepsilon$.
506 The space consumed by the heap need not be linear in the \em{current} number
507 of items, but if a~case where this matters ever occured, we could fix it easily
508 by rebuilding the whole data structure completely after $n/2$ deletes. This
509 increases the number of potentially corrupted items, but at worst twice, so it
510 suffices to decrease~$\varepsilon$ twice.