From a12357a5e472737350fb8be3f655f3ede2de1953 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 28 Mar 2008 00:04:22 +0100 Subject: [PATCH] Analysis of soft heaps finished. --- opt.tex | 53 +++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 45 insertions(+), 8 deletions(-) diff --git a/opt.tex b/opt.tex index 4f58c5f..a3ce088 100644 --- a/opt.tex +++ b/opt.tex @@ -289,7 +289,7 @@ has disappeared since $\(v)>r$ and therefore the desired bound is at least We will now sum the sizes of the lists over all vertices containing corrupted items. -\lemma +\lemma\id{shcorrlemma}% At any given time, the heap contains at most~$n/2^{r-2}$ corrupted items. \proof @@ -324,10 +324,10 @@ this makes less than $n_k/2^{k-2}$ corrupted items as we asserted. \paran{Analysis of time complexity} Now we will analyse the amortized time complexity of the individual operations. -We will show that if we charge $\O(r)$ time on every element inserted, it suffices +We will show that if we charge $\O(r)$ time against every element inserted, it suffices to cover the cost of all other operations. We take a~look at the melds first. -\lemma +\lemma\id{shmeld}% The amortized cost of a~meld is $\O(1)$, except for melds induced by dismantling which take $\O(\(q))$, where $q$~is the queue to be dismantled. @@ -335,7 +335,7 @@ which take $\O(\(q))$, where $q$~is the queue to be dismantled. The real cost of a~meld of heaps $P$ and~$Q$ is the smaller of their ranks plus the time spent on carry propagation. The latter is easy to dispose of: since every time there is a~carry, the total number of trees in all heaps decreases -by one, it suffices to charge $\O(1)$ on creation of a~tree. An~insert creates +by one, it suffices to charge $\O(1)$ against creation of a~tree. An~insert creates one tree, dismantling creates at most $\(q)$ trees, all other operations alter only the internal structure of trees. @@ -351,7 +351,7 @@ in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the rank twice, because the ranks of right sons on every path from the root of the tree to a~leaf are strictly decreasing. (This holds because melding two heaps of the same rank always produces a~heap of higher rank.) Hence at most~$n/2^k$ -right sons have rank~$k$ and the total time charged to the leaves is bounded by: +right sons have rank~$k$ and the total time charged against the leaves is bounded by: $$ \sum_{k=0}^{\rm max. rank}k\cdot {n\over 2^k} \le n\cdot\sum_{k=0}^\infty {k\over 2^k} = \O(n). $$ @@ -363,7 +363,7 @@ by induced melds, the above calculation is still a~proper upper bound on the cos of the regular melds. \qed -To estimate the time spent on deletions, we first analyse the refills. +To estimate the time spent on deletions, we analyse the refills first. \lemma Every call of the \ procedure spends time $\O(1)$ amortized. @@ -402,12 +402,49 @@ so it is clearly dominated by the other possibilities. \>The total cost of all operations on the upper part is therefore $\O(n)$. \qed -It remains to analyse the rest of the \ operation. +It remains to examine the rest of the \ operation. -\lemma +\lemma\id{shdelmin}% Every \ takes $\O(1)$ time amortized. \proof +Aside from refilling, which is $\O(1)$ by the previous lemma, the \ +takes care of the Rank invariant. This happens by checking the length of the leftmost +path and dismantling the tree if the length is too far from the tree's rank~$k$. +The leftmost path is however always visited by the call to \, so we can +account the check on the refilling. The same holds for disassembling. We then have +to pay $\O(k)$ for melding the trees back to the heap, but since there are at most +$k/2$ trees, a~subtree of rank at least $k/2$ must have been deleted. This tree +contained at least $2^{k/2}$ vertices which are now permanently gone from the +data structure, so we can charge the cost of the meld against these vertices. + +We must not forget that \ also has to recalculate the suffix minima. +In the worst case, it requires touching $k$~trees. Because of the Rank invariant, +this is linear in the size of the +leftmost path and therefore it can be also paid for by \. (Incidentally, +this was the only place where we needed the invariant.) +\qed + +Now we can put the bits together and laurel our effort with the following theorem: + +\thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}} +A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes +a~sequence of operations starting with an~empty heap and containing $n$~\s +in time $\O(n\log(1/\varepsilon))$. At every moment, the heap contains at most +$\varepsilon n$ corrupted items. + +\proof +We set the parameter~$r$ to~$2+2\lceil\log (1/\varepsilon)\rceil$. The rest follows +from the analysis above. By Lemma \ref{shcorrlemma}, there are always at most $n/2^{r-2} +\le \varepsilon n$ corrupted items in the heap. By Lemma \ref{shmeld}--\ref{shdelmin}, +the time spent on all operations in the sequence can be paid for by charging $\O(r)$ time +against each \, which yields the time bound. \qed +\FIXME{Remark on optimality.} + +\FIXME{Example of use: pivots.} + + + \endpart -- 2.39.2