]> mj.ucw.cz Git - saga.git/blob - ram.tex
Improved proof of QH lemma.
[saga.git] / ram.tex
1 \ifx\endpart\undefined
2 \input macros.tex
3 \fi
4
5 \chapter{Fine Details of Computation}
6 \id{ramchap}
7
8 \section{Models and machines}
9
10 Traditionally, computer scientists use a~variety of computational models
11 as a~formalism in which their algorithms are stated. If we were studying
12 NP-completeness, we could safely assume that all the models are equivalent,
13 possibly up to polynomial slowdown which is negligible. In our case, the
14 differences between good and not-so-good algorithms are on a~much smaller
15 scale. In this chapter, we will replace the usual ``yardsticks'' by a~micrometer,
16 state our computation models carefully and develop a repertoire of basic
17 data structures taking advantage of the fine details of the models.
18
19 We would like to keep the formalism close enough to the reality of the contemporary
20 computers. This rules out Turing machines and similar sequentially addressed
21 models, but even the remaining models are subtly different from each other. For example, some of them
22 allow indexing of arrays in constant time, while on the others,
23 arrays have to be emulated with pointer structures, requiring $\Omega(\log n)$
24 time to access a~single element of an~$n$-element array. It is hard to say which
25 way is superior --- while most ``real'' computers have instructions for constant-time
26 indexing, it seems to be physically impossible to fulfil this promise regardless of
27 the size of memory. Indeed, at the level of logical gates inside the computer,
28 the depth of the actual indexing circuits is logarithmic.
29
30 In recent decades, most researchers in the area of combinatorial algorithms
31 have been considering two computational models: the Random Access Machine and the Pointer
32 Machine. The former is closer to the programmer's view of a~real computer,
33 the latter is slightly more restricted and ``asymptotically safe.''
34 We will follow this practice and study our algorithms in both models.
35
36 \para
37 The \df{Random Access Machine (RAM)} is not a~single coherent model, but rather a~family
38 of closely related machines, sharing the following properties.
39 (See Cook and Reckhow \cite{cook:ram} for one of the usual formal definitions
40 and Hagerup \cite{hagerup:wordram} for a~thorough description of the differences
41 between the RAM variants.)
42
43 The \df{memory} of the machine is represented by an~array of \df{memory cells}
44 addressed by non-negative integers, each of them containing a~single non-negative integer.
45 The \df{program} is a~finite sequence of \df{instructions} of two basic kinds: calculation
46 instructions and control instructions.
47
48 \df{Calculation instructions} have two source arguments and one destination
49 argument, each \df{argument} being either an~immediate constant (not available
50 as destination), a~directly addressed memory cell (specified by its number)
51 or an~indirectly addressed memory cell (its address is stored in a~directly
52 addressed memory cell).
53
54 \df{Control instructions} include branches (to a~specific instruction in
55 the program), conditional branches (e.g., jump if two arguments specified as
56 in the calculation instructions are equal) and an~instruction to halt the program.
57
58 At the beginning of the computation, the memory contains the input data
59 in specified cells and arbitrary values in all other cells.
60 Then the program is executed one instruction at a~time. When it halts,
61 specified memory cells are interpreted as the program's output.
62
63 \para\id{wordsize}%
64 In the description of the RAM family, we have omitted several details
65 on~purpose, because different members of the family define them differently.
66 These are: the size of the available integers, the time complexity of a~single
67 instruction, the space complexity assigned to a~single memory cell and the set
68 of operations available in calculation instructions.
69
70 If we impose no limits on the magnitude of the numbers and we assume that
71 arithmetic and logical operations work on them in constant time, we get
72 a~very powerful parallel computer --- we can emulate an~exponential number
73 of parallel processors using arithmetics and suddenly almost everything can be
74 computed in constant time, modulo encoding and decoding of input and output.
75 Such models are unrealistic and there are two basic possibilities how to
76 avoid this behavior:
77
78 \numlist\ndotted
79 \:Keep unbounded numbers, but increase costs of instructions: each instruction
80   consumes time proportional to the number of bits of the numbers it processes,
81   including memory addresses. Similarly, space usage is measured in bits,
82   counting not only the values, but also the addresses of the respective memory
83   cells.
84 \:Place a~limit on the size of the numbers ---define the \df{word size~$W$,}
85   the number of bits available in the memory cells--- and keep the cost of
86   instructions and memory cells constant. The word size must not be constant,
87   since we can address only~$2^W$ cells of memory. If the input of the algorithm
88   is stored in~$N$ cells, we need~$W\ge\log N$ just to be able to read the input.
89   On the other hand, we are interested in polynomial-time algorithms only, so $\Theta(\log N)$-bit
90   numbers should be sufficient. In practice, we pick~$W$ to be the larger of
91   $\Theta(\log N)$ and the size of integers used in the algorithm's input and output.
92   We will call an integer which fits in a~single memory cell a~\df{machine word.}
93 \endlist
94
95 Both restrictions easily avoid the problems of unbounded parallelism. The first
96 choice is theoretically cleaner and Cook et al.~show nice correspondences to the
97 standard complexity classes, but the calculations of time and space complexity tend
98 to be somewhat tedious. What more, when compared with the RAM with restricted
99 word size, the complexities are usually exactly $\Theta(W)$ times higher.
100 This does not hold in general (consider a~program which uses many small numbers
101 and $\O(1)$ large ones), but it is true for the algorithms we are interested in.
102 Therefore we will always assume that the operations have unit cost and we make
103 sure that all numbers are limited by the available word size.
104
105 \para
106 As for the choice of RAM operations, the following three instruction sets are often used:
107
108 \itemize\ibull
109 \:\df{Word-RAM} --- allows the ``C-language operators'', i.e., addition,
110   subtraction, multiplication, division, remainder, bitwise $\band$, $\bor$, exclusive
111   $\bor$ ($\bxor$) and negation ($\bnot$), and bitwise shifts ($\shl$ and~$\shr$).
112 \:\df{${\rm AC}^0$-RAM} --- allows all operations from the class ${\rm AC}^0$, i.e.,
113   those computable by constant-depth polynomial-size boolean circuits with unlimited
114   fan-in and fan-out. This includes all operations of the Word-RAM except for multiplication,
115   division and remainders, and also many other operations like computing the Hamming
116   weight (number of bits set in a~given number).
117 \:Both restrictions at once.
118 \endlist
119
120 Thorup discusses the usual techniques employed by RAM algorithms in~\cite{thorup:aczero}
121 and he shows that they work on both Word-RAM and ${\rm AC}^0$-RAM, but the combination
122 of the two restrictions is too weak. On the other hand, the intersection of~${\rm AC}^0$
123 with the instruction set of modern processors is already strong enough (e.g., when we
124 add some floating-point operations and multimedia instructions available on the Intel's
125 Pentium~4~\cite{intel:pentium}).
126
127 We will therefore use the Word-RAM instruction set, mentioning differences from the
128 ${\rm AC}^0$-RAM where necessary.
129
130 \nota
131 When speaking of the \df{RAM,} we implicitly mean the version with numbers limited
132 by a~specified word size of $W$~bits, unit cost of operations and memory cells and the instruction
133 set of the Word-RAM. This corresponds to the usage in recent algorithmic literature,
134 although the authors rarely mention the details. In some cases, a~non-uniform variant
135 of the Word-RAM is considered as well (e.g., in~\cite{hagerup:dd}):
136
137 \defn\id{nonuniform}%
138 A~Word-RAM is called \df{weakly non-uniform,} if it is equipped with $\O(1)$-time
139 access to a~constant number of word-sized constants, which depend only on the word
140 size. These are called \df{native constants} and they are available in fixed memory
141 cells when the program starts. (By analogy with the high-level programming languages,
142 these constants can be thought of as computed at ``compile time.'')
143
144 \para
145 The \df{Pointer Machine (PM)} also does not have any well established definition. The
146 various kinds of pointer machines are mapped by Ben-Amram in~\cite{benamram:pm},
147 but unlike the RAM's they turn out to be equivalent up to constant slowdown.
148 Our definition will be closely related to the \em{linking automaton} proposed
149 by Knuth in~\cite{knuth:fundalg}, we will only adapt it to use RAM-like
150 instructions instead of an~opaque control unit.
151
152 The PM works with two different types of data: \df{symbols} from a~finite alphabet
153 and \df{pointers}. The memory of the machine consists of a~fixed amount of \df{registers}
154 (some of them capable of storing a~single symbol, each of the others holds a~single pointer)
155 and an~arbitrary amount of \df{cells}. The structure of all cells is the same: each of them
156 again contains a~fixed number of fields for symbols and pointers. Registers can be addressed
157 directly, the cells only via pointers --- by using a~pointer stored either in a~register,
158 or in a~cell pointed to by a~register (longer chains of pointers cannot be followed in
159 constant time).
160
161 We can therefore view the whole memory as a~directed graph, whose vertices
162 correspond to the cells (the registers are stored in a~single special cell).
163 The outgoing edges of each vertex correspond to pointer fields of the cells and they are
164 labeled with distinct labels drawn from a~finite set. In addition to that,
165 each vertex contains a~fixed amount of symbols. The program can directly access
166 vertices within distance~2 from the register vertex.
167
168 The program is a~finite sequence of instructions of the following kinds:
169
170 \itemize\ibull
171 \:\df{symbol instructions,} which read a~pair of symbols, apply an~arbitrary
172   function on them and write the result to a~symbol register or field;
173 \:\df{pointer instructions} for assignment of pointers to pointer registers/fields
174   and for creation of new memory cells (a~pointer to the new cell is assigned
175   immediately);
176 \:\df{control instructions} --- similarly to the RAM; conditional jumps can decide
177   on~arbitrary unary relations on symbols and compare pointers for equality.
178 \endlist
179
180 Time and space complexity are defined in the straightforward way: all instructions
181 have unit cost and so do all memory cells.
182
183 Both input and output of the machine are passed in the form of a~linked structure
184 pointed to by a~designated register. For example, we can pass graphs back and forth
185 without having to encode them as strings of numbers or symbols. This is important,
186 because with the finite alphabet of the~PM, symbolic representations of graphs
187 generally require super-linear space and therefore also time.\foot{%
188 The usual representation of edges as pairs of vertex labels uses $\Theta(m\log n)$ bits
189 and as a~simple counting argument shows, this is asymptotically optimal for general
190 sparse graphs. On the other hand, specific families of sparse graphs can be stored
191 more efficiently, e.g., by a~remarkable result of Tur\'an~\cite{turan:succinct},
192 planar graphs can be encoded in~$\O(n)$ bits. Encoding of dense graphs is of
193 course trivial as the adjacency matrix has only~$\Theta(n^2)$ bits.}
194
195 \para
196 Compared to the RAM, the PM lacks two important capabilities: indexing of arrays
197 and arithmetic instructions. We can emulate both with poly-logarithmic slowdown,
198 but it will turn out that they are rarely needed in graph algorithms. We are
199 also going to prove that the RAM is strictly stronger, so we will prefer to
200 formulate our algorithms in the PM model and use RAM only when necessary.
201
202 \thm
203 Every program for the Word-RAM with word size~$W$ can be translated to a~PM program
204 computing the same with $\O(W^2)$ slowdown (given a~suitable encoding of inputs and
205 outputs, of course). If the RAM program does not use multiplication, division
206 and remainder operations, $\O(W)$~slowdown is sufficient.
207
208 \proofsketch
209 Represent the memory of the RAM by a~balanced binary search tree or by a~radix
210 trie of depth~$\O(W)$. Values are encoded as~linked lists of symbols pointed
211 to by the nodes of the tree. Both direct and indirect accesses to the memory
212 can therefore be done in~$\O(W)$ time. Use standard algorithms for arithmetic
213 on big numbers: $\O(W)$ per operation except for multiplication, division and
214 remainders which take $\O(W^2)$.\foot{We could use more efficient arithmetic
215 algorithms, but the quadratic bound is good enough for our purposes.}
216 \qed
217
218 \FIXME{Add references, especially to the unbounded parallelism remark.}
219
220 \thm
221 Every program for the PM running in polynomial time can be translated to a~program
222 computing the same on the Word-RAM with only $\O(1)$ slowdown.
223
224 \proofsketch
225 Encode each cell of the PM's memory to $\O(1)$ integers. Store the encoded cells to
226 the memory of the RAM sequentially and use memory addresses as pointers. As the symbols
227 are finite and there is only a~polynomial number of cells allocated during execution
228 of the program, $\O(\log N)$-bit integers suffice ($N$~is the size of the program's input).
229 \qed
230
231 \para
232 There are also \df{randomized} versions of both machines. These are equipped
233 with an~additional instruction for generating a~single random bit. The standard
234 techniques of design and analysis of randomized algorithms apply (see for
235 example Motwani and Raghavan~\cite{motwani:randalg}).
236
237 \FIXME{Consult sources. Does it make more sense to generate random words at once on the RAM?}
238
239 \rem
240 There is one more interesting machine: the \df{Immutable Pointer Machine} (see
241 the description of LISP machines in \cite{benamram:pm}). It differs from the
242 ordinary PM by the inability to modify existing memory cells. Only the contents
243 of the registers are allowed to change. All cell modifications thus have to
244 be performed by creating a~copy of the particular cell with some fields changed.
245 This in turn requires the pointers to the cell to be updated, possibly triggering
246 a~cascade of further cell copies. For example, when a~node of a~binary search tree is
247 updated, all nodes on the path from that node to the root have to be copied.
248
249 One of the advantages of this model is that the states of the machine are
250 persistent --- it is possible to return to a~previously visited state by recalling
251 the $\O(1)$ values of the registers (everything else could not have changed
252 since that time) and ``fork'' the computations. This corresponds to the semantics
253 of pure functional languages, e.g., Haskell~\cite{jones:haskell}.
254
255 Unless we are willing to accept a~logarithmic penalty in execution time and space
256 (in fact, our emulation of the Word-RAM on the PM can be easily made immutable),
257 the design of efficient algorithms for the immutable PM requires very different
258 techniques. Therefore, we will concentrate on the imperative models instead
259 and refer the interested reader to the thorough treatment of purely functional
260 data structures in the Okasaki's monograph~\cite{okasaki:funcds}.
261
262 %--------------------------------------------------------------------------------
263
264 \section{Bucket sorting and contractions}\id{bucketsort}%
265
266 The Contractive Bor\o{u}vka's algorithm (\ref{contbor}) needed to contract a~given
267 set of edges in the current graph and flatten it afterwards, all this in time $\O(m)$.
268 We have spared the technical details for this section and they will be useful
269 in further algorithms, too.
270
271 As already suggested, the contractions can be performed by building an~auxiliary
272 graph and finding its connected components. Thus we will take care of the flattening
273 only.
274
275 \para
276 On the RAM, it is sufficient to sort the edges lexicographically (each edge viewed
277 as an~ordered pair of vertex identifiers with the smaller of the identifiers placed
278 first). We can do that by a two-pass bucket sort with~$n$ buckets corresponding
279 to the vertex identifiers.
280
281 However, there is a~catch in this. Suppose that we use the standard representation
282 of graphs by adjacency lists whose heads are stored in an array indexed by vertex
283 identifiers. When we contract and flatten the graph, the number of vertices decreases,
284 but if we inherit the original vertex identifiers, the arrays will still have the
285 same size. Hence we spend a~super-linear amount of time on scanning the increasingly
286 sparse arrays, most of the time skipping unused entries.
287
288 To avoid this, we have to renumber the vertices after each contraction to component
289 identifiers from the auxiliary graph and we create a~new vertex array. This way,
290 the representation of the graph will be kept linear with respect to the size of the
291 current graph.
292
293 \para
294 The pointer representation of graphs does not suffer from sparsity as the vertices
295 are always identified by pointers to per-vertex structures. Each such structure
296 then contains all attributes associated with the vertex, including the head of its
297 adjacency list. However, we have to find a~way how to perform bucket sorting
298 without arrays.
299
300 We will keep a~list of the per-vertex structures which defines the order of~vertices.
301 Each such structure will contain a~pointer to the head of the corresponding bucket,
302 again stored as a~list. Putting an~edge to a~bucket can be done in constant time then,
303 scanning all~$n$ buckets takes $\O(n+m)$ time.
304
305 \FIXME{Add an example of locally determined orders, e.g., tree isomorphism?}
306
307 %--------------------------------------------------------------------------------
308
309 \section{Data structures on the RAM}
310
311 There is a~lot of data structures designed specifically for the RAM, taking
312 advantage of both indexing and arithmetics. In many cases, they surpass the known
313 lower bounds for the same problem on the~PM and they often achieve constant time
314 per operation, at least when either the magnitude of the values or the size of
315 the data structure are suitably bounded.
316
317 A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt},
318 which represent a~subset of the integers $\{0,\ldots,U-1\}$, allowing insertion,
319 deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$,
320 regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's
321 algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm
322 for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$,
323 where $w_{max}$ is the maximum weight. We will show later that it is even
324 possible to achieve linear time complexity for arbitrary integer weights.
325
326 A~real breakthrough has been made by Fredman and Willard, who introduced
327 the Fusion trees~\cite{fw:fusion} which again perform membership and predecessor
328 operation on a~set of $n$~integers, but this time with complexity $\O(\log_W n)$
329 per operation on a~Word-RAM with $W$-bit words. This of course assumes that
330 each element of the set fits in a~single word. As $W$ must at least~$\log n$,
331 the operations take $\O(\log n/\log\log n)$ and we are able to sort $n$~integers
332 in time~$o(n\log n)$. This was a~beginning of a~long sequence of faster and
333 faster sorting algorithms, culminating with the work by Thorup and Han.
334 They have improved the time complexity of integer sorting to $\O(n\log\log n)$ deterministically~\cite{han:detsort}
335 and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:randsort},
336 both in linear space.
337
338 Despite the recent progress, the corner-stone of most RAM data structures
339 is still the representation of data structures by integers introduced by Fredman
340 and Willard. It will also form a~basis for the rest of this chapter.
341
342 \FIXME{Add more history.}
343
344 %--------------------------------------------------------------------------------
345
346 \section{Bits and vectors}\id{bitsect}
347
348 In this rather technical section, we will show how the RAM can be used as a~vector
349 computer to operate in parallel on multiple elements, as long as these elements
350 fit in a~single machine word. At the first sight this might seem useless, because we
351 cannot require large word sizes, but surprisingly often the elements are small
352 enough relative to the size of the algorithm's input and thus also relative to
353 the minimum possible word size. Also, as the following lemma shows, we can
354 easily emulate slightly longer words:
355
356 \lemman{Multiple-precision calculations}
357 Given a~RAM with $W$-bit words, we can emulate all calculation and control
358 instructions of a~RAM with word size $kW$ in time depending only on the~$k$.
359 (This is usually called \df{multiple-precision arithmetics.})
360
361 \proof
362 We split each word of the ``big'' machine to $W'$-bit blocks, where $W'=W/2$, and store these
363 blocks in $2k$ consecutive memory cells. Addition, subtraction, comparison and
364 bitwise logical operations can be performed block-by-block. Shifts by a~multiple
365 of~$W'$ are trivial, otherwise we can combine each block of the result from
366 shifted versions of two original blocks.
367 To multiply two numbers, we can use the elementary school algorithm using the $W'$-bit
368 blocks as digits in base $2^{W'}$ --- the product of any two blocks fits
369 in a~single word.
370
371 Division is harder, but Newton-Raphson iteration (see~\cite{ito:newrap})
372 converges to the quotient in a~constant number of iterations, each of them
373 involving $\O(1)$ multiple-precision additions and multiplications. A~good
374 starting approximation can be obtained by dividing the two most-significant
375 (non-zero) blocks of both numbers.
376
377 Another approach to division is using the improved elementary school algorithm as described
378 by Knuth in~\cite{knuth:seminalg}. It uses $\O(k^2)$ steps, but the steps involve
379 calculation of the most significant bit set in a~word. We will show below that it
380 can be done in constant time, but we have to be careful to avoid division instructions.
381 \qed
382
383 \notan{Bit strings}\id{bitnota}%
384 We will work with binary representations of natural numbers by strings over the
385 alphabet $\{\0,\1\}$: we will use $\(x)$ for the number~$x$ written in binary,
386 $\(x)_b$ for the same padded to exactly $b$ bits by adding leading zeroes,
387 and $x[k]$ for the value of the $k$-th bit of~$x$ (with a~numbering of bits such that $2^k[k]=1$).
388 The usual conventions for operations on strings will be utilized: When $s$
389 and~$t$ are strings, we write $st$ for their concatenation and
390 $s^k$ for the string~$s$ repeated $k$~times.
391 When the meaning is clear from the context,
392 we will use $x$ and $\(x)$ interchangeably to avoid outbreak of symbols.
393
394 \defn
395 The \df{bitwise encoding} of a~vector ${\bf x}=(x_0,\ldots,x_{d-1})$ of~$b$-bit numbers
396 is an~integer~$x$ such that $\(x)=\(x_{d-1})_b\0\(x_{d-2})_b\0\ldots\0\(x_0)_b$, i.e.,
397 $x = \sum_i 2^{(b+1)i}\cdot x_i$. (We have interspersed the elements with \df{separator bits.})
398
399 \notan{Vectors}\id{vecnota}%
400 We will use boldface letters for vectors and the same letters in normal type
401 for their encodings. The elements of a~vector~${\bf x}$ will be written as
402 $x_0,\ldots,x_{d-1}$.
403
404 \para
405 If we want to fit the whole vector in a~single word, the parameters $b$ and~$d$ must satisty
406 the condition $(b+1)d\le W$.
407 By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
408 We will now describe how to translate simple vector manipulations to sequences of $\O(1)$ RAM operations
409 on their codes. As we are interested in asymptotic complexity only, we prefer clarity
410 of the algorithms over saving instructions. Among other things, we freely use calculations
411 on words of size $\O(bd)$, assuming that the Multiple-precision lemma comes to save us
412 when necessary.
413
414 \para
415 First of all, let us observe that we can use $\band$ and $\bor$ with suitable constants
416 to write zeroes or ones to an~arbitrary set of bit positions at once. These operations
417 are usually called \df{bit masking}. Also, any element of a~vector can be extracted or
418 replaced by a~different value in $\O(1)$ time by masking and shifts.
419
420 \newdimen\slotwd
421 \def\setslot#1{\setbox0=#1\slotwd=\wd0}
422 \def\slot#1{\hbox to \slotwd{\hfil #1\hfil}}
423 \def\[#1]{\slot{$#1$}}
424 \def\9{\rack{\0}{\hss$\cdot$\hss}}
425
426 \def\alik#1{%
427 \medskip
428 \halign{\hskip 0.15\hsize\hfil $ ##$&\hbox to 0.6\hsize{${}##$ \hss}\cr
429 #1}
430 \medskip
431 }
432
433 \algn{Operations on vectors with $d$~elements of $b$~bits each}\id{vecops}
434
435 \itemize\ibull
436
437 \:$\<Replicate>(\alpha)$ --- creates a~vector $(\alpha,\ldots,\alpha)$:
438
439 \alik{\<Replicate>(\alpha)=\alpha\cdot(\0^b\1)^d. \cr}
440
441 \:$\<Sum>(x)$ --- calculates the sum of the elements of~${\bf x}$, assuming that
442 the result fits in $b$~bits:
443
444 \alik{\<Sum>(x) = x \bmod \1^{b+1}. \cr}
445
446 This is correct because when we calculate modulo~$\1^{b+1}$, the number $2^{b+1}=\1\0^{b+1}$
447 is congruent to~1 and thus $x = \sum_i 2^{(b+1)i}\cdot x_i \equiv \sum_i 1^i\cdot x_i \equiv \sum_i x_i$.
448 As the result should fit in $b$~bits, the modulo makes no difference.
449
450 If we want to avoid division, we can use double-precision multiplication instead:
451
452 \setslot{\hbox{~$\0x_{d-1}$}}
453 \def\.{\[]}
454 \def\z{\[\0^b\1]}
455 \def\dd{\slot{$\cdots$}}
456 \def\vd{\slot{$\vdots$}}
457 \def\rule{\noalign{\medskip\nointerlineskip}$\hrulefill$\cr\noalign{\nointerlineskip\medskip}}
458
459 \alik{
460 \[\0x_{d-1}] \dd \[\0x_2] \[\0x_1] \[\0x_0] \cr
461 *~~ \z \dd \z\z\z \cr
462 \rule
463 \[x_{d-1}] \dd \[x_2] \[x_1] \[x_0] \cr
464 \[x_{d-1}] \[x_{d-2}] \dd \[x_1] \[x_0] \. \cr
465 \[x_{d-1}] \[x_{d-2}] \[x_{d-3}] \dd \[x_0] \. \. \cr
466 \vd\vd\vd\vd\.\.\.\cr
467 \[x_{d-1}] \dd \[x_2]\[x_1]\[x_0] \. \. \. \. \cr
468 \rule
469 \[r_{d-1}] \dd \[r_2] \[r_1] \[s_d] \dd \[s_3] \[s_2] \[s_1] \cr
470 }
471
472 This way, we even get the vector of all partial sums:
473 $s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{d-1}x_i$.
474
475 \:$\<Cmp>(x,y)$ --- element-wise comparison of~vectors ${\bf x}$ and~${\bf y}$,
476 i.e., a~vector ${\bf z}$ such that $z_i=1$ if $x_i<y_i$ and $z_i=0$ otherwise.
477
478 We replace the separator zeroes in~$x$ by ones and subtract~$y$. These ones
479 change back to zeroes exactly at the positions where $x_i<y_i$ and they stop
480 carries from propagating, so the fields do not interact with each other:
481
482 \setslot{\vbox{\hbox{~$x_{d-1}$}\hbox{~$y_{d-1}$}}}
483 \def\9{\rack{\0}{\hss ?\hss}}
484 \alik{
485    \1 \[x_{d-1}] \1 \[x_{d-2}] \[\cdots] \1 \[x_1] \1 \[x_0]  \cr
486 -~ \0 \[y_{d-1}] \0 \[y_{d-2}] \[\cdots] \0 \[y_1] \0 \[y_0]  \cr
487 \rule
488    \9 \[\ldots]  \9 \[\ldots]  \[\cdots] \9 \[\ldots] \9 \[\ldots] \cr
489 }
490
491 It only remains to shift the separator bits to the right positions, negate them
492 and mask out all other bits.
493
494 \:$\<Rank>(x,\alpha)$ --- returns the number of elements of~${\bf x}$ which are less than~$\alpha$,
495 assuming that the result fits in~$b$ bits:
496
497 \alik{
498 \<Rank>(x,\alpha) = \<Sum>(\<Cmp>(x,\<Replicate>(\alpha))). \cr
499 }
500
501 \:$\<Insert>(x,\alpha)$ --- inserts~$\alpha$ into a~sorted vector $\bf x$:
502
503 We calculate the rank of~$\alpha$ in~$x$ first, then we insert~$\alpha$ as the $k$-th
504 field of~$\bf x$ using masking operations and shifts.
505
506 \algo
507 \:$k\=\<Rank>(x,\alpha)$.
508 \:$\ell\=x \band \1^{(b+1)(n-k-1)}\0^{(b+1)(k+1)}$. \cmt{``left'' part of the vector}
509 \:$r=x \band \1^{(b+1)k}$. \cmt{``right'' part}
510 \:Return $(\ell\shl (b+1)) \bor (\alpha\shl ((b+1)k)) \bor r$.
511 \endalgo
512
513 \:$\<Unpack>(\alpha)$ --- creates a~vector whose elements are the bits of~$\(\alpha)_d$.
514 In other words, inserts blocks~$\0^b$ between the bits of~$\alpha$. Assuming that $b\ge d$,
515 we can do it as follows:
516
517 \algo
518 \:$x\=\<Replicate>(\alpha)$.
519 \:$y\=(2^{b-1},2^{b-2},\ldots,2^0)$. \cmt{bitwise encoding of this vector}
520 \:$z\=x \band y$.
521 \:Return $\<Cmp>(z,y)$.
522 \endalgo
523
524 Let us observe that $z_i$ is either zero or equal to~$y_i$ depending on the value
525 of the $i$-th bit of the number~$\alpha$. Comparing it with~$y_i$ normalizes it
526 to either zero or one.
527
528 \:$\<Unpack>_\pi(\alpha)$ --- like \<Unpack>, but changes the order of the
529 bits according to a~fixed permutation~$\pi$: The $i$-th element of the
530 resulting vector is equal to~$\alpha[\pi(i)]$.
531
532 Implemented as above, but with a~mask $y=(2^{\pi(b-1)},\ldots,2^{\pi(0)})$.
533
534 \:$\<Pack>(x)$ --- the inverse of \<Unpack>: given a~vector of zeroes and ones,
535 it produces a~number whose bits are the elements of the vector (in other words,
536 it crosses out the $\0^b$ blocks).
537
538 We interpret the~$x$ as an~encoding of a~vector with elements one bit shorter
539 and we sum these elements. For example, when $n=4$ and~$b=4$:
540
541 \setslot{\hbox{$x_3$}}
542 \def\z{\[\0]}
543 \def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
544 \def\.{\hphantom{\|}}
545
546 \alik{
547 \|\z\.\z\.\z\.\z\.\[x_3]\|\z\.\z\.\z\.\z\.\[x_2]\|\z\.\z\.\z\.\z\[x_1]\|\z\.\z\.\z\.\z\.\[x_0]\|\cr
548 \|\z\.\z\.\z\.\z\|\[x_3]\.\z\.\z\.\z\|\z\.\[x_2]\.\z\.\z\|\z\.\z\[x_1]\.\z\|\z\.\z\.\z\.\[x_0]\|\cr
549 }
550
551 However, this ``reformatting'' does not produce a~correct encoding of a~vector,
552 because the separator zeroes are missing. For this reason, the implementation
553 of~\<Sum> using modulo does not work correctly (it produces $\0^b$ instead of $\1^b$).
554 We therefore use the technique based on multiplication instead, which does not need
555 the separators. (Alternatively, we can observe that $\1^b$ is the only case
556 affected, so we can handle it separately.)
557
558 \endlist
559
560 \para
561 We can use the aforementioned tricks to perform interesting operations on individual
562 numbers in constant time, too. Let us assume for a~while that we are
563 operating on $b$-bit numbers and the word size is at least~$b^2$.
564 This enables us to make use of intermediate vectors with $b$~elements
565 of $b$~bits each.
566
567 \algn{Integer operations in quadratic workspace}\id{lsbmsb}
568
569 \itemize\ibull
570
571 \:$\<Weight>(\alpha)$ --- computes the Hamming weight of~$\alpha$, i.e., the number of ones in~$\(\alpha)$.
572
573 We perform \<Unpack> and then \<Sum>.
574
575 \:$\<Permute>_\pi(\alpha)$ --- shuffles the bits of~$\alpha$ according
576 to a~fixed permutation~$\pi$.
577
578 We perform $\<Unpack>_\pi$ and \<Pack> back.
579
580 \:$\<LSB>(\alpha)$ --- finds the least significant bit of~$\alpha$,
581 i.e., the smallest~$i$ such that $\alpha[i]=1$.
582
583 By a~combination of subtraction with $\bxor$, we create a~number
584 which contains ones exactly at the position of $\<LSB>(\alpha)$ and below:
585
586 \alik{
587 \alpha&=                        \9\9\9\9\9\1\0\0\0\0\cr
588 \alpha-1&=                      \9\9\9\9\9\0\1\1\1\1\cr
589 \alpha\bxor(\alpha-1)&=         \0\9\9\9\0\1\1\1\1\1\cr
590 }
591
592 Then we calculate the \<Weight> of the result and subtract~1.
593
594 \:$\<MSB>(\alpha)$ --- finds the most significant bit of~$\alpha$ (the position
595 of the highest bit set).
596
597 Reverse the bits of the number~$\alpha$ first by calling \<Permute>, then apply \<LSB>
598 and subtract the result from~$b-1$.
599
600 \endlist
601
602 \rem
603 As noted by Brodnik~\cite{brodnik:lsb} and others, the space requirements of
604 the \<LSB> operation can be reduced to linear. We split the input to $\sqrt{b}$
605 blocks of $\sqrt{b}$ bits each. Then we determine which blocks are non-zero and
606 identify the lowest such block (this is a~\<LSB> of a~number whose bits
607 correspond to the blocks). Finally we calculate the \<LSB> of this block. In
608 both calls to \<LSB,> we have a $\sqrt{b}$-bit number in a~$b$-bit word, so we
609 can use the previous algorithm. The same trick of course works for finding the
610 \<MSB> as well.
611
612 The following algorithm shows the details.
613
614 \algn{LSB in linear workspace}
615
616 \algo\id{lsb}
617 \algin A~$w$-bit number~$\alpha$.
618 \:$b\=\lceil\sqrt{w}\,\rceil$. \cmt{size of a~block}
619 \:$\ell\=b$. \cmt{the number of blocks is the same}
620 \:$x\=(\alpha \band (\0\1^b)^\ell) \bor (\alpha \band (\1\0^b)^\ell)$.
621 \hfill\break
622 \cmt{encoding of a~vector~${\bf x}$ such that $x_i\ne 0$ iff the $i$-th block is non-zero}%
623 \foot{Why is this so complicated? It is tempting to take $\alpha$ itself as a~code of this vector,
624 but we unfortunately need the separator bits between elements, so we create them and
625 relocate the bits we have overwritten.}
626 \:$y\=\<Cmp>(0,x)$. \cmt{$y_i=1$ if the $i$-th block is non-zero, otherwise $y_0=0$}
627 \:$\beta\=\<Pack>(y)$. \cmt{each block compressed to a~single bit}
628 \:$p\=\<LSB>(\beta)$. \cmt{the index of the lowest non-zero block}
629 \:$\gamma\=(\alpha \shr bp) \band \1^b$. \cmt{the contents of that block}
630 \:$q\=\<LSB>(\gamma)$. \cmt{the lowest bit set there}
631 \algout $\<LSB>(\alpha) = bp+q$.
632 \endalgo
633
634 \rem
635 We have used a~plenty of constants which depend on the format of the vectors.
636 Either we can write non-uniform programs (see \ref{nonuniform}) and use native constants,
637 or we can observe that all such constants can be easily manufactured. For example,
638 $(\0^b\1)^d = \1^{(b+1)d} / \1^{b+1} = (2^{(b+1)d}-1)/(2^{b+1}-1)$. The only exceptions
639 are the~$w$ and~$b$ in the LSB algorithm \ref{lsb}, which we are unable to produce
640 in constant time. In practice we use the ``bit tricks'' as frequently called subroutines
641 in an~encompassing algorithm, so we usually can spend a~lot of time on the precalculation
642 of constants performed once during algorithm startup.
643
644 %--------------------------------------------------------------------------------
645
646 \section{Q-Heaps}\id{qheaps}%
647
648 We have shown how to perform non-trivial operations on a~set of values
649 in constant time, but so far only under the assumption that the number of these
650 values is small enough and that the values themselves are also small enough
651 (so that the whole set fits in $\O(1)$ machine words). Now we will show how to
652 lift the restriction on the magnitude of the values and still keep constant time
653 complexity. We will describe a~slightly simplified version of the Q-heaps developed by
654 Fredman and Willard in~\cite{fw:transdich}.
655
656 The Q-heap represents a~set of at most~$k$ word-sized integers, where $k\le W^{1/4}$
657 and $W$ is the word size of the machine. It will support insertion, deletion, finding
658 of minimum and maximum, and other operations described below, in constant time, provided that
659 we are willing to spend~$\O(2^{k^4})$ time on preprocessing.
660
661 The exponential-time preprocessing may sound alarming, but a~typical application uses
662 Q-heaps of size $k=\log^{1/4} N$, where $N$ is the size of the algorithm's input.
663 This guarantees that $k\le W^{1/4}$ and $\O(2^{k^4}) = \O(N)$. Let us however
664 remark that the whole construction is primarily of theoretical importance
665 and that the huge constants involved everywhere make these heaps useless
666 in practical algorithms. Many of the tricks used however prove themselves
667 useful even in real-life implementations.
668
669 Spending the time on reprocessing makes it possible to precompute tables for
670 almost arbitrary functions and then assume that they can be evaluated in
671 constant time:
672
673 \lemma\id{qhprecomp}%
674 When~$f$ is a~function computable in polynomial time, $\O(2^{k^4})$ time is enough
675 to precompute a~table of the values of~$f$ for all arguments whose size is $\O(k^3)$ bits.
676
677 \proof
678 There are $2^{\O(k^3)}$ possible combinations of arguments of the given size and for each of
679 them we spend $\O(k^c)$ time by calculating the function (for some~$c\ge 1$). It remains
680 to observe that $2^{\O(k^3)}\cdot \O(k^c) = \O(2^{k^4})$.
681 \qed
682
683 \para
684 We will first show an~auxiliary construction based on tries and then derive
685 the real definition of the Q-heap from it.
686
687 \nota
688 Let us introduce some notation first:
689 \itemize\ibull
690 \:$W$ --- the word size of the RAM,
691 \:$k = \O(W^{1/4})$ --- the limit on the size of the heap,
692 \:$n\le k$ --- the number of elements stored in the heap,
693 \:$X=\{x_1, \ldots, x_n\}$ --- the elements themselves: distinct $W$-bit numbers
694 indexed in a~way that $x_1 < \ldots < x_n$,
695 \:$g_i = \<MSB>(x_i \bxor x_{i+1})$ --- the position of the most significant bit in which $x_i$ and~$x_{i+1}$ differ,
696 \:$R_X(x)$ --- the rank of~$x$ in~$X$, that is the number of elements of~$X$ which are less than~$x$
697 (where $x$~itself need not be an~element of~$X$).\foot{We will dedicate the whole chapter \ref{rankchap} to the
698 study of various ranks.}
699 \endlist
700
701 \defn
702 A~\df{trie} for a~set of strings~$S$ over a~finite alphabet~$\Sigma$ is
703 a~rooted tree whose vertices are the prefixes of the strings in~$S$ and there
704 is an~edge going from a~prefix~$\alpha$ to a~prefix~$\beta$ iff $\beta$ can be
705 obtained from~$\alpha$ by appending a~single symbol of the alphabet. The edge
706 will be labeled with the particular symbol. We will also define the~\df{letter depth}
707 of a~vertex as the length of the corresponding prefix. We mark the vertices
708 which match a~string of~$S$.
709
710 A~\df{compressed trie} is obtained from the trie by removing the vertices of outdegree~1
711 except for the root and marked vertices.
712 Whereever is a~directed path whose internal vertices have outdegree~1 and they carry
713 no mark, we replace this path by a~single edge labeled with the contatenation
714 of the original edge's labels.
715
716 In both kinds of tries, we order the outgoing edges of every vertex by their labels
717 lexicographically.
718
719 \obs
720 In both tries, the root of the tree is the empty word and for every other vertex, the
721 corresponding prefix is equal to the concatenation of edge labels on the path
722 leading from the root to that vertex. The letter depth of the vertex is equal to
723 the total size of these labels. All leaves correspond to strings in~$S$, but so can
724 some internal vertices if there are two strings in~$S$ such that one is a~prefix
725 of the other.
726
727 Furthermore, the labels of all edges leaving a~common vertex are always
728 distinct and when we compress the trie, no two such labels have share their initial
729 symbols. This allows us to search in the trie efficiently: when looking for
730 a~string~$x$, we follow the path from the root and whenever we visit
731 an~internal vertex of letter depth~$d$, we test the $d$-th character of~$x$,
732 we follow the edge whose label starts with this character, and we check that the
733 rest of the label matches.
734
735 The compressed trie is also efficient in terms of space consumption --- it has
736 $\O(\vert S\vert)$ vertices (this can be easily shown by induction on~$\vert S\vert$)
737 and all edge labels can be represented in space linear in the sum of the
738 lengths of the strings in~$S$.
739
740 \defn
741 For our set~$X$, we define~$T$ as a~compressed trie for the set of binary
742 encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W ; x\in X \}$.
743
744 \obs
745 The trie~$T$ has several interesting properties. Since all words in~$S$ have the same
746 length, the leaves of the trie correspond to these exact words, that is to the numbers~$x_i$.
747 The inorder traversal of the trie enumerates the words of~$S$ in lexicographic order
748 and therefore also the~$x_i$'s in the order of their values. Between each
749 pair of leaves $x_i$ and~$x_{i+1}$ it visits an~internal vertex whose letter depth
750 is exactly~$W-1-g_i$.
751
752 \para
753 Let us now modify the algorithm for searching in the trie and make it compare
754 only the first symbols of the edges. In other words, we will test only the bits~$g_i$
755 which will be called \df{guides} (as they guide us through the tree). For $x\in
756 X$, the modified algorithm will still return the correct leaf. For all~$x$ outside~$X$
757 it will no longer fail and instead it will land on some leaf~$x_i$. At the
758 first sight the number~$x_i$ may seem unrelated, but we will show that it can be
759 used to determine the rank of~$x$ in~$X$, which will later form a~basis for all
760 Q-heap operations:
761
762 \lemma\id{qhdeterm}%
763 The rank $R_X(x)$ is uniquely determined by a~combination of:
764 \itemize\ibull
765 \:the trie~$T$,
766 \:the index~$i$ of the leaf found when searching for~$x$ in~$T$,
767 \:the relation ($<$, $=$, $>$) between $x$ and $x_i$,
768 \:the bit position $b=\<MSB>(x\bxor x_i)$ of the first disagreement between~$x$ and~$x_i$.
769 \endlist
770
771 \proof
772 If $x\in X$, we detect that from $x_i=x$ and the rank is obviously~$i-1$.
773 Let us assume that $x\not\in X$ and imagine that we follow the same path as when
774 searching for~$x$,
775 but this time we check the full edge labels. The position~$b$ is the first position
776 where~$\(x)$ disagrees with a~label. Before this point, all edges not taken by
777 the search were leading either to subtrees containing elements all smaller than~$x$
778 or all larger than~$x$ and the only values not known yet are those in the subtree
779 below the edge which we currently consider. Now if $x[b]=0$ (and therefore $x<x_i$),
780 all values in that subtree have $x_j[b]=1$ and thus they are larger than~$x$. In the other
781 case, $x[b]=1$ and $x_j[b]=0$, so they are smaller.
782 \qed
783
784 \para
785 The preceding lemma shows that the rank can be computed in polynomial time, but
786 unfortunately the variables on which it depends are too large for a~table to
787 be efficiently precomputed. We will carefully choose an~equivalent representation
788 of the trie which is compact enough.
789
790 \lemma\id{citree}%
791 The trie is uniquely determined by the order of the guides~$g_1,\ldots,g_{n-1}$.
792
793 \proof
794 We already know that the letter depths of the trie vertices are exactly
795 the numbers~$W-1-g_i$. The root of the trie must have the smallest of these
796 letter depths, i.e., it must correspond to the highest numbered bit. Let
797 us call this bit~$g_i$. This implies that the values $x_1,\ldots,x_i$
798 must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its
799 right subtree. Both subtrees can be then constructed recursively.\foot{This
800 construction is also known as the \df{cartesian tree} for the sequence
801 $g_1,\ldots,g_n$.}
802 \qed
803
804 \para
805 Unfortunately, the vector of the $g_i$'s is also too long (is has $k\log W$ bits
806 and we have no upper bound on~$W$ in terms of~$k$), so we will compress it even
807 further:
808
809 \nota
810 \itemize\ibull
811 \:$B = \{g_1,\ldots,g_n\}$ --- the set of bit positions of all the guides, stored as a~sorted array,
812 \:$G : \{1,\ldots,n\} \rightarrow \{1,\ldots,n\}$ --- a~function mapping
813 the guides to their bit positions in~$B$: $g_i = B[G(i)]$,
814 \:$x[B]$ --- a~bit string containing the bits of~$x$ originally located
815 at the positions given by~$B$, i.e., the concatenation of bits $x[B[1]],
816 x[B[2]],\ldots, x[B[n]]$.
817 \endlist
818
819 \obs\id{qhsetb}%
820 The set~$B$ has $\O(k\log W)=\O(W)$ bits, so it can be stored in a~constant number
821 of machine words in form of a~sorted vector. The function~$G$ can be also stored as a~vector
822 of $\O(k\log k)$ bits. We can change a~single~$g_i$ in constant time using
823 vector operations: First we delete the original value of~$g_i$ from~$B$ if it
824 is not used anywhere else. Then we add the new value to~$B$ if it was not
825 there yet and we write its position in~$B$ to~$G(i)$. Whenever we insert
826 or delete a~value in~$B$, the values at the higher positions shift one position
827 up or down and we have to update the pointers in~$G$. This can be fortunately
828 accomplished by adding or subtracting a~result of vector comparison.
829
830 In this representation, we can reformulate our lemma on ranks as follows:
831
832 \lemma\id{qhrank}%
833 The rank $R_X(x)$ can be computed in constant time from:
834 \itemize\ibull
835 \:the function~$G$,
836 \:the values $x_1,\ldots,x_n$,
837 \:the bit string~$x[B]$,
838 \:$x$ itself.
839 \endlist
840
841 \proof
842 Let us prove that all ingredients of Lemma~\ref{qhdeterm} are either small
843 enough or computable in constant time.
844
845 We know that the shape of the trie~$T$ is uniquely determined by the order of the $g_i$'s
846 and therefore by the function~$G$ since the array~$B$ is sorted. The shape of
847 the trie together with the bits in $x[B]$ determine the leaf~$x_i$ found when searching
848 for~$x$ using only the guides. This can be computed in polynomial time and it
849 depends on $\O(k\log k)$ bits of input, so according to Lemma~\ref{qhprecomp}
850 we can look it up in a~precomputed table.
851
852 The relation between $x$ and~$x_i$ can be obtained directly as we know the~$x_i$.
853 The bit position of the first disagreement can be calculated in constant time
854 using the LSB/MSB algorithm (\ref{lsb}).
855
856 All these ingredients can be stored in $\O(k\log k)$ bits, so we may assume
857 that the rank can be looked up in constant time as well.
858 \qed
859
860 \para
861 In the Q-heap we would like to store the set~$X$ as a~sorted array together
862 with the corresponding trie, which will allow us to determine the position
863 for a~newly inserted element in constant time. However, the set is too large
864 to fit in a~vector and we cannot perform insertion on an~ordinary array in
865 constant time. This can be worked around by keeping the set in an~unsorted
866 array together with a~vector containing the permutation which sorts the array.
867 We can then insert a~new element at an~arbitrary place in the array and just
868 update the permutation to reflect the correct order.
869
870 We are now ready for the real definition of the Q-heap and for the description
871 of the basic operations on it.
872
873 \defn
874 A~\df{Q-heap} consists of:
875 \itemize\ibull
876 \:$k$, $n$ --- the capacity of the heap and the current number of elements (word-sized integers),
877 \:$X$ --- the set of word-sized elements stored in the heap (an~array of words in an~arbitrary order),
878 \:$\varrho$ --- a~permutation on~$\{1,\ldots,n\}$ such that $X[\varrho(1)] < \ldots < X[\varrho(n)]$
879 (a~vector of $\O(n\log k)$ bits; we will write $x_i$ for $X[\varrho(i)]$),
880 \:$B$ --- a~set of ``interesting'' bit positions
881 (a~sorted vector of~$\O(n\log W)$ bits),
882 \:$G$ --- the function which maps the guides to the bit positions in~$B$
883 (a~vector of~$\O(n\log k)$ bits),
884 \:precomputed tables of various functions.
885 \endlist
886
887 \algn{Search in the Q-heap}\id{qhfirst}%
888 \algo
889 \algin A~Q-heap and an~integer~$x$ to search for.
890 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
891 \:If $i\le n$ return $x_i$, otherwise return {\sc undefined.}
892 \algout The smallest element of the heap which is greater or equal to~$x$.
893 \endalgo
894
895 \algn{Insertion to the Q-heap}
896 \algo
897 \algin A~Q-heap and an~integer~$x$ to insert.
898 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
899 \:If $x=x_i$, return immediately (the value is already present).
900 \:Insert the new value to~$X$:
901 \::$n\=n+1$.
902 \::$X[n]\=x$.
903 \::Insert~$n$ at the $i$-th position in the permutation~$\varrho$.
904 \:Update the $g_j$'s:
905 \::Move all~$g_j$ for $j\ge i$ one position up. \hfil\break
906    This translates to insertion in the vector representing~$G$.
907 \::Recalculate $g_{i-1}$ and~$g_i$ according to the definition.
908    \hfil\break Update~$B$ and~$G$ as described in~\ref{qhsetb}.
909 \algout The updated Q-heap.
910 \endalgo
911
912 \algn{Deletion from the Q-heap}
913 \algo
914 \algin A~Q-heap and an~integer~$x$ to be deleted from it.
915 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
916 \:If $i>n$ or $x_i\ne x$, return immediately (the value is not in the heap).
917 \:Delete the value from~$X$:
918 \::$X[\varrho(i)]\=X[n]$.
919 \::Find $j$ such that~$\varrho(j)=n$ and set $\varrho(j)\=\varrho(i)$.
920 \::$n\=n-1$.
921 \:Update the $g_j$'s like in the previous algorithm.
922 \algout The updated Q-heap.
923 \endalgo
924
925 \algn{Finding the $i$-th smallest element in the Q-heap}\id{qhlast}%
926 \algo
927 \algin A~Q-heap and an~index~$i$.
928 \:If $i<1$ or $i>n$, return {\sc undefined.}
929 \:Return~$x_i$.
930 \algout The $i$-th smallest element in the heap.
931 \endalgo
932
933 \para
934 The heap algorithms we have just described have been built from primitives
935 operating in constant time, with one notable exception: the extraction
936 $x[B]$ of all bits of~$x$ at positions specified by the set~$B$. This cannot be done
937 in~$\O(1)$ time on the Word-RAM, but we can implement it with ${\rm AC}^0$
938 instructions as suggested by Andersson in \cite{andersson:fusion} or even
939 with those ${\rm AC}^0$ instructions present on real processors (see Thorup
940 \cite{thorup:aczero}). On the Word-RAM, we need to make use of the fact
941 that the set~$B$ is not changing too much --- there are $\O(1)$ changes
942 per Q-heap operation. As Fredman and Willard have shown, it is possible
943 to maintain a~``decoder'', whose state is stored in $\O(1)$ machine words,
944 and which helps us to extract $x[B]$ in a~constant number of operations:
945
946 \lemman{Extraction of bits}\id{qhxtract}%
947 Under the assumptions on~$k$, $W$ and the preprocessing time as in the Q-heaps,\foot{%
948 Actually, this is the only place where we need~$k$ to be as low as $W^{1/4}$.
949 In the ${\rm AC}^0$ implementation, it is enough to ensure $k\log k\le W$.
950 On the other hand, we need not care about the exponent because it can
951 be arbitrarily increased using the Q-heap trees described below.}
952 it is possible to maintain a~data structure for a~set~$B$ of bit positions,
953 which allows~$x[B]$ to be extracted in $\O(1)$ time for an~arbitrary~$x$.
954 When a~single element is inserted to~$B$ or deleted from~$B$, the structure
955 can be updated in constant time, as long as $\vert B\vert \le k$.
956
957 \proof
958 See Fredman and Willard \cite{fw:transdich}.
959 \qed
960
961 \para
962 This was the last missing bit of the mechanics of the Q-heaps. We are
963 therefore ready to conclude this section by the following theorem
964 and its consequences:
965
966 \thmn{Q-heaps, Fredman and Willard \cite{fw:transdich}}\id{qh}%
967 Let $W$ and~$k$ be positive integers such that $k=\O(W^{1/4})$. Let~$Q$
968 be a~Q-heap of at most $k$-elements of $W$~bits each. Then the Q-heap
969 operations \ref{qhfirst} to \ref{qhlast} on~$Q$ (insertion, deletion,
970 search for a~given value and search for the $i$-th smallest element)
971 run in constant time on a~Word-RAM with word size~$W$, after spending
972 time $\O(2^{k^4})$ on the same RAM on precomputing of tables.
973
974 \proof
975 Every operation on the Q-heap can be performed in a~constant number of
976 vector operations and calculations of ranks. The ranks are computed
977 in $\O(1)$ steps involving again $\O(1)$ vector operations, binary
978 logarithms and bit extraction. All these can be calculated in constant
979 time using the results of section \ref{bitsect} and Lemma \ref{qhxtract}.
980 \qed
981
982 \rem
983 We can also use the Q-heaps as building blocks of more complex structures
984 like Atomic heaps and AF-heaps (see once again \cite{fw:transdich}). We will
985 show a~simpler, but useful construction, sometimes called the \df{Q-heap tree.}
986 Suppose we have a~Q-heap of capacity~$k$ and a~parameter $d\in{\bb N}^+$. We
987 can build a~balanced $k$-ary tree of depth~$d$ such that its leaves contain
988 a~given set and every internal vertex keeps the minimum value in the subtree
989 rooted in it, together with a~Q-heap containing the values in all its sons.
990 This allows minimum to be extracted in constant time (it is placed in the root)
991 and when any element is changed, it is sufficient to recalculate the values
992 from the path from this element to the root, which takes $\O(d)$ Q-heap
993 operations.
994
995 \corn{Q-heap trees}\id{qhtree}%
996 For every positive integer~$r$ and $\delta>0$ there exists a~data structure
997 capable of maintaining the minimum of a~set of at most~$r$ word-sized numbers
998 under insertions and deletions. Each operation takes $\O(1)$ time on a~Word-RAM
999 with word size $W=\Omega(r^{\delta})$, after spending time
1000 $\O(2^{r^\delta})$ on precomputing of tables.
1001
1002 \proof
1003 Choose $\delta' \le \delta$ such that $r^{\delta'} = \O(W^{1/4})$. Build
1004 a~Q-heap tree of depth $d=\lceil \delta/\delta'\rceil$ containing Q-heaps of
1005 size $k=r^{\delta'}$. \qed
1006
1007 \rem\id{qhtreerem}%
1008 When we have an~algorithm with input of size~$N$, the word size is at least~$\log N$
1009 and we can spend time $\O(N)$ on preprocessing, so we can choose $r=\log N$ and
1010 $\delta=1$ in the above corollary and get a~heap of size $\log N$ working in
1011 constant time per operation.
1012
1013 \endpart