From baeb4ba6b8e8cb7af56453e388715453824865a3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 27 Mar 2008 13:49:41 +0100 Subject: [PATCH] Soft heaps: time complexity. --- opt.tex | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 66 insertions(+), 8 deletions(-) diff --git a/opt.tex b/opt.tex index ce1ecd6..d624e85 100644 --- a/opt.tex +++ b/opt.tex @@ -94,7 +94,11 @@ We will now combine the soft queues to the soft heap. of those following it in the list; \:and a~global parameter~$r\in{\bb N}$, to be set depending on~$\varepsilon$. \endlist -\>The heap always keeps the \df{Rank invariant:} When a~root of a~tree has rank~$k$, + +\>We will define the \df{rank} of a~heap as the highest of the ranks of its queues +(that is, the rank of the heap's tail). + +The heap always keeps the \df{Rank invariant:} When a~root of any tree has rank~$k$, its leftmost path has length at least~$k/2$. \para @@ -121,9 +125,10 @@ a~single-element heap and melding it to the destination heap. \algn{Melding of two soft heaps} \algo \algin Two soft heaps~$P$ and~$Q$. -\:If the tail of~$P$ has smaller rank than the tail of~$Q$, exchange their item lists. -\brk\cmt{Whenever we run into an~end of a~list, we assume that it contains an~empty queue of infinite rank.} +\:If the heap~$P$ has smaller rank than the heap~$Q$, exchange their item lists. \:$p\=\(P)$. +\brk\cmt{Whenever we run into an~end of a~list in this procedure, we assume that it contains +an~empty queue of infinite rank.} \:While $Q$ still has some queues: \::$q\=\(Q)$. \::If $\(p) < \(q)$, then $p\=$ the successor of~$p$, @@ -253,10 +258,11 @@ Let us translate these ideas to real (pseudo)code: \paran{Analysis of accuracy} The description of the operations is complete, let us analyse their behavior and verify that we have delivered what we promised --- first the accuracy of -the structure, then the time complexity of operations. +the structure, then the time complexity of operations. In the whole analysis, +we will denote the total number of elements inserted in the history of the +structure by~$n$. We will also assume that the threshold~$r$ is even. -We start with bounding the size of the item lists. We will assume that -the threshold~$r$ is even. +We start by bounding the size of the item lists. \lemma For every vertex~$v$ of a~soft queue, the size $\ell(v)$ of its item list @@ -284,8 +290,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 -After~$n$ items have been inserted, the heap contains at most~$n/2^{r-2}$ corrupted -items at any given time. +At any given time, the heap contains at most~$n/2^{r-2}$ corrupted items. \proof We first prove an~auxiliary claim: The master trees of all queues contain at most~$n$ @@ -318,6 +323,59 @@ this makes less than $n_k/2^{k-2}$ corrupted items as we asserted. \qed \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 +to cover the cost of all other operations. We take a~look at the melds first. +\lemma +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. + +\proof +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 +one tree, dismantling creates at most $\(q)$ trees, all other operations +alter only the internal structure of trees. + +As for the $\O(\min(\(P),\(Q)))$ part, let us assume for a~while that +no dismantling ever takes place and consider the \df{meld forest.} It is a~forest +whose leaves correspond to the $n$~single-element heaps constructed by \ +and each internal vertex represents a~heap arisen from melding its sons. The left +son will be the one with the greater (or equal) rank. We therefore want to bound +the sum of ranks of all right sons. + +For every right son, we will distribute the change for its rank~$k$ on all leaves +in its subtree. There are at least $2^k$ such leaves. No leaf ever receives the same +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: +$$ +\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). +$$ + +Let us return dismantling to the game. When a~queue is dismantled, melding the parts +back to the heap takes $\O(\(q))$ time. We can therefore let the dismantling pay for it +and omit such induced melds from the meld forest. As the rank of the heap is never increased +by induced melds, the above calculation is still a~proper upper bound on the cost +of the regular melds. +\qed + +To estimate the time spent on deletions, we first analyse the refills. + +\lemma +Every call of the \ procedure spends time $\O(1)$ amortized. + +\proof +Every call of \ can be split to the bottom part (rank~$r$ and below) and the +upper part. Whenever we recurse on the bottom part when processing the upper one, +we spend at most~$\O(r)$ time there. We will show that + +We will prove that all refills together take time $\O(nr)$, which will be charged on the +inserts. + +\qed \endpart -- 2.39.2