5 \chapter{Fine Details of Computation}
8 \section{Models and machines}
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.
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.
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.
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.)
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.
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).
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.
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.
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.
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
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
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 that fits in a~single memory cell a~\df{machine word.}
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 that 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.
106 As for the choice of RAM operations, the following three instruction sets are often used:
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.
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}).
127 We will therefore use the Word-RAM instruction set, mentioning differences from the
128 ${\rm AC}^0$-RAM where necessary.
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}):
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.'')
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.
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
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.
168 The program is a~finite sequence of instructions of the following kinds:
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
176 \:\df{control instructions} --- similarly to the RAM; conditional jumps can decide
177 on~arbitrary unary relations on symbols and compare pointers for equality.
180 Time and space complexity are defined in the straightforward way: all instructions
181 have unit cost and so do all memory cells.
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.}
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.
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.
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.}
218 \FIXME{Add references, especially to the unbounded parallelism remark.}
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.
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).
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}).
237 \FIXME{Consult sources. Does it make more sense to generate random words at once on the RAM?}
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.
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}.
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}.
262 %--------------------------------------------------------------------------------
264 \section{Bucket sorting and unification}\id{bucketsort}%
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, in which we are going to
269 explain several techniques based on bucket sorting. These will be useful in further
272 As already suggested in the proof of Lemma \ref{contbor}, contractions can be performed
273 in linear time by building an~auxiliary graph and finding its connected components.
274 We will thus take care only of the subsequent flattening.
276 \paran{Flattening on RAM}%
277 On the RAM, we can view the edges as ordered pairs of vertex identifiers with the
278 smaller of the identifiers placed first and sort them lexicographically. This brings
279 parallel edges together, so that a~simple linear scan suffices to find each bunch
280 of parallel edges and remove all but the lightest one.
281 Lexicographic sorting of pairs can be accomplished in linear time by a~two-pass
282 bucket sort with $n$~buckets corresponding to the vertex identifiers.
284 However, there is a~catch in this. Suppose that we use the standard representation
285 of graphs by adjacency lists whose heads are stored in an array indexed by vertex
286 identifiers. When we contract and flatten the graph, the number of vertices decreases,
287 but if we inherit the original vertex identifiers, the arrays will still have the
288 same size. We could then waste a~super-linear amount of time by scanning the increasingly
289 sparse arrays, most of the time skipping unused entries.
291 To avoid this problem, we have to renumber the vertices after each contraction to component
292 identifiers from the auxiliary graph and create a~new vertex array. This helps to
293 keep the size of the representation of the graph linear with respect to its current
296 \paran{Flattening on PM}%
297 The pointer representation of graphs does not suffer from sparsity since the vertices
298 are always identified by pointers to per-vertex structures. Each such structure
299 then contains all attributes associated with the vertex, including the head of its
300 adjacency list. However, we have to find a~way how to perform bucket sorting
301 without indexing of arrays.
303 We will keep a~list of the per-vertex structures that defines the order of~vertices.
304 Each such structure will be endowed with a~pointer to the head of the list of items in
305 the corresponding bucket. Inserting an~edge to a~bucket can be then done in constant time
306 and scanning all~$n$ buckets takes $\O(n+m)$ time.
308 \paran{Tree isomorphism}%
309 Another nice example of pointer-based radix sorting is a~pointer algorithm for
310 deciding whether two rooted trees are isomorphic. Let us assume for a~moment that
311 the outdegree of each vertex is at most a~fixed constant~$k$. We sort the subtrees
312 of both trees by their depth by running the depth-first search to calculate the
313 depths and bucket-sorting them with $n$~buckets afterwards.
315 Then we proceed from depth~1 to the maximum depth and for each of them we identify
316 the isomorphism classes of subtrees of that particular depth. We will assign some
317 sort of identifiers to the classes; at most~$n+1$ of them are needed as there are
318 $n+1$~subtrees in the tree (including the empty subtree). As the PM does not
319 have numbers as a~first-class type, we just create a~list of $n+1$~distinct items
320 and use pointers to these items as identifiers. Isomorphism of the whole trees
321 can be finally decided by comparing the identifiers assigned to their roots.
323 Suppose that classes of depths $1,\ldots,d-1$ are already computed and we want
324 to identify those of depth~$d$. We take a~root of every such tree and label it
325 with an~ordered $k$-tuple of identifiers of its subtrees; when it has less than
326 $k$ sons, we pad the tuple with empty subtrees. Tuples corresponding to isomorphic
327 subtrees are identical up to reordering of elements. We therefore sort the codes
328 inside each tuple and then sort the tuples, which brings the equivalent tuples
331 The first sort (inside the tuples) would be easy on the RAM, but on the PM we
332 have no means of comparing two identifiers for anything else than equality.
333 We work around this by sorting the set $\{ (x,i,j) \mid \hbox{$x$ is the $i$-th
334 element of the $j$-th tuple} \}$ on~$x$, reset all tuples and insert the elements
335 back in the increasing order of~$x$.
343 \FIXME{Buchsbaum's trick}
345 %--------------------------------------------------------------------------------
347 \section{Data structures on the RAM}
350 There is a~lot of data structures designed specifically for the RAM, taking
351 advantage of both indexing and arithmetics. In many cases, they surpass the known
352 lower bounds for the same problem on the~PM and they often achieve constant time
353 per operation, at least when either the magnitude of the values or the size of
354 the data structure are suitably bounded.
356 A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt},
357 which represent a~subset of the integers $\{0,\ldots,U-1\}$, allowing insertion,
358 deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$,
359 regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's
360 algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm
361 for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$,
362 where $w_{max}$ is the maximum weight. We will show later that it is even
363 possible to achieve linear time complexity for arbitrary integer weights.
365 A~real breakthrough has been made by Fredman and Willard, who introduced
366 the Fusion trees~\cite{fw:fusion} which again perform membership and predecessor
367 operation on a~set of $n$~integers, but this time with complexity $\O(\log_W n)$
368 per operation on a~Word-RAM with $W$-bit words. This of course assumes that
369 each element of the set fits in a~single word. As $W$ must at least~$\log n$,
370 the operations take $\O(\log n/\log\log n)$ and we are able to sort $n$~integers
371 in time~$o(n\log n)$. This was a~beginning of a~long sequence of faster and
372 faster sorting algorithms, culminating with the work by Thorup and Han.
373 They have improved the time complexity of integer sorting to $\O(n\log\log n)$ deterministically~\cite{han:detsort}
374 and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:randsort},
375 both in linear space.
377 Despite the recent progress, the corner-stone of most RAM data structures
378 is still the representation of data structures by integers introduced by Fredman
379 and Willard. It will also form a~basis for the rest of this chapter.
381 \FIXME{Add more history.}
383 %--------------------------------------------------------------------------------
385 \section{Bits and vectors}\id{bitsect}
387 In this rather technical section, we will show how the RAM can be used as a~vector
388 computer to operate in parallel on multiple elements, as long as these elements
389 fit in a~single machine word. At the first sight this might seem useless, because we
390 cannot require large word sizes, but surprisingly often the elements are small
391 enough relative to the size of the algorithm's input and thus also relative to
392 the minimum possible word size. Also, as the following lemma shows, we can
393 easily emulate slightly longer words:
395 \lemman{Multiple-precision calculations}
396 Given a~RAM with $W$-bit words, we can emulate all calculation and control
397 instructions of a~RAM with word size $kW$ in time depending only on the~$k$.
398 (This is usually called \df{multiple-precision arithmetics.})
401 We split each word of the ``big'' machine to $W'$-bit blocks, where $W'=W/2$, and store these
402 blocks in $2k$ consecutive memory cells. Addition, subtraction, comparison and
403 bitwise logical operations can be performed block-by-block. Shifts by a~multiple
404 of~$W'$ are trivial, otherwise we can combine each block of the result from
405 shifted versions of two original blocks.
406 To multiply two numbers, we can use the elementary school algorithm using the $W'$-bit
407 blocks as digits in base $2^{W'}$ --- the product of any two blocks fits
410 Division is harder, but Newton-Raphson iteration (see~\cite{ito:newrap})
411 converges to the quotient in a~constant number of iterations, each of them
412 involving $\O(1)$ multiple-precision additions and multiplications. A~good
413 starting approximation can be obtained by dividing the two most-significant
414 (non-zero) blocks of both numbers.
416 Another approach to division is using the improved elementary school algorithm as described
417 by Knuth in~\cite{knuth:seminalg}. It uses $\O(k^2)$ steps, but the steps involve
418 calculation of the most significant bit set in a~word. We will show below that it
419 can be done in constant time, but we have to be careful to avoid division instructions.
422 \notan{Bit strings}\id{bitnota}%
423 We will work with binary representations of natural numbers by strings over the
424 alphabet $\{\0,\1\}$: we will use $\(x)$ for the number~$x$ written in binary,
425 $\(x)_b$ for the same padded to exactly $b$ bits by adding leading zeroes,
426 and $x[k]$ for the value of the $k$-th bit of~$x$ (with a~numbering of bits such that $2^k[k]=1$).
427 The usual conventions for operations on strings will be utilized: When $s$
428 and~$t$ are strings, we write $st$ for their concatenation and
429 $s^k$ for the string~$s$ repeated $k$~times.
430 When the meaning is clear from the context,
431 we will use $x$ and $\(x)$ interchangeably to avoid outbreak of symbols.
434 The \df{bitwise encoding} of a~vector ${\bf x}=(x_0,\ldots,x_{d-1})$ of~$b$-bit numbers
435 is an~integer~$x$ such that $\(x)=\(x_{d-1})_b\0\(x_{d-2})_b\0\ldots\0\(x_0)_b$, i.e.,
436 $x = \sum_i 2^{(b+1)i}\cdot x_i$. (We have interspersed the elements with \df{separator bits.})
438 \notan{Vectors}\id{vecnota}%
439 We will use boldface letters for vectors and the same letters in normal type
440 for their encodings. The elements of a~vector~${\bf x}$ will be written as
441 $x_0,\ldots,x_{d-1}$.
444 If we want to fit the whole vector in a~single word, the parameters $b$ and~$d$ must satisty
445 the condition $(b+1)d\le W$.
446 By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
447 We will now describe how to translate simple vector manipulations to sequences of $\O(1)$ RAM operations
448 on their codes. As we are interested in asymptotic complexity only, we prefer clarity
449 of the algorithms over saving instructions. Among other things, we freely use calculations
450 on words of size $\O(bd)$, assuming that the Multiple-precision lemma comes to save us
454 First of all, let us observe that we can use $\band$ and $\bor$ with suitable constants
455 to write zeroes or ones to an~arbitrary set of bit positions at once. These operations
456 are usually called \df{bit masking}. Also, any element of a~vector can be extracted or
457 replaced by a~different value in $\O(1)$ time by masking and shifts.
460 \def\setslot#1{\setbox0=#1\slotwd=\wd0}
461 \def\slot#1{\hbox to \slotwd{\hfil #1\hfil}}
462 \def\[#1]{\slot{$#1$}}
463 \def\9{\rack{\0}{\hss$\cdot$\hss}}
467 \halign{\hskip 0.15\hsize\hfil $ ##$&\hbox to 0.6\hsize{${}##$ \hss}\cr
472 \algn{Operations on vectors with $d$~elements of $b$~bits each}\id{vecops}
476 \:$\<Replicate>(\alpha)$ --- creates a~vector $(\alpha,\ldots,\alpha)$:
478 \alik{\<Replicate>(\alpha)=\alpha\cdot(\0^b\1)^d. \cr}
480 \:$\<Sum>(x)$ --- calculates the sum of the elements of~${\bf x}$, assuming that
481 the result fits in $b$~bits:
483 \alik{\<Sum>(x) = x \bmod \1^{b+1}. \cr}
485 This is correct because when we calculate modulo~$\1^{b+1}$, the number $2^{b+1}=\1\0^{b+1}$
486 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$.
487 As the result should fit in $b$~bits, the modulo makes no difference.
489 If we want to avoid division, we can use double-precision multiplication instead:
491 \setslot{\hbox{~$\0x_{d-1}$}}
494 \def\dd{\slot{$\cdots$}}
495 \def\vd{\slot{$\vdots$}}
496 \def\rule{\noalign{\medskip\nointerlineskip}$\hrulefill$\cr\noalign{\nointerlineskip\medskip}}
499 \[\0x_{d-1}] \dd \[\0x_2] \[\0x_1] \[\0x_0] \cr
500 *~~ \z \dd \z\z\z \cr
502 \[x_{d-1}] \dd \[x_2] \[x_1] \[x_0] \cr
503 \[x_{d-1}] \[x_{d-2}] \dd \[x_1] \[x_0] \. \cr
504 \[x_{d-1}] \[x_{d-2}] \[x_{d-3}] \dd \[x_0] \. \. \cr
505 \vd\vd\vd\vd\.\.\.\cr
506 \[x_{d-1}] \dd \[x_2]\[x_1]\[x_0] \. \. \. \. \cr
508 \[r_{d-1}] \dd \[r_2] \[r_1] \[s_d] \dd \[s_3] \[s_2] \[s_1] \cr
511 This way, we even get the vector of all partial sums:
512 $s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{d-1}x_i$.
514 \:$\<Cmp>(x,y)$ --- element-wise comparison of~vectors ${\bf x}$ and~${\bf y}$,
515 i.e., a~vector ${\bf z}$ such that $z_i=1$ if $x_i<y_i$ and $z_i=0$ otherwise.
517 We replace the separator zeroes in~$x$ by ones and subtract~$y$. These ones
518 change back to zeroes exactly at the positions where $x_i<y_i$ and they stop
519 carries from propagating, so the fields do not interact with each other:
521 \setslot{\vbox{\hbox{~$x_{d-1}$}\hbox{~$y_{d-1}$}}}
522 \def\9{\rack{\0}{\hss ?\hss}}
524 \1 \[x_{d-1}] \1 \[x_{d-2}] \[\cdots] \1 \[x_1] \1 \[x_0] \cr
525 -~ \0 \[y_{d-1}] \0 \[y_{d-2}] \[\cdots] \0 \[y_1] \0 \[y_0] \cr
527 \9 \[\ldots] \9 \[\ldots] \[\cdots] \9 \[\ldots] \9 \[\ldots] \cr
530 It only remains to shift the separator bits to the right positions, negate them
531 and mask out all other bits.
533 \:$\<Rank>(x,\alpha)$ --- returns the number of elements of~${\bf x}$ which are less than~$\alpha$,
534 assuming that the result fits in~$b$ bits:
537 \<Rank>(x,\alpha) = \<Sum>(\<Cmp>(x,\<Replicate>(\alpha))). \cr
540 \:$\<Insert>(x,\alpha)$ --- inserts~$\alpha$ into a~sorted vector $\bf x$:
542 We calculate the rank of~$\alpha$ in~$x$ first, then we insert~$\alpha$ as the $k$-th
543 field of~$\bf x$ using masking operations and shifts.
546 \:$k\=\<Rank>(x,\alpha)$.
547 \:$\ell\=x \band \1^{(b+1)(n-k-1)}\0^{(b+1)(k+1)}$. \cmt{``left'' part of the vector}
548 \:$r=x \band \1^{(b+1)k}$. \cmt{``right'' part}
549 \:Return $(\ell\shl (b+1)) \bor (\alpha\shl ((b+1)k)) \bor r$.
552 \:$\<Unpack>(\alpha)$ --- creates a~vector whose elements are the bits of~$\(\alpha)_d$.
553 In other words, inserts blocks~$\0^b$ between the bits of~$\alpha$. Assuming that $b\ge d$,
554 we can do it as follows:
557 \:$x\=\<Replicate>(\alpha)$.
558 \:$y\=(2^{b-1},2^{b-2},\ldots,2^0)$. \cmt{bitwise encoding of this vector}
560 \:Return $\<Cmp>(z,y)$.
563 Let us observe that $z_i$ is either zero or equal to~$y_i$ depending on the value
564 of the $i$-th bit of the number~$\alpha$. Comparing it with~$y_i$ normalizes it
565 to either zero or one.
567 \:$\<Unpack>_\pi(\alpha)$ --- like \<Unpack>, but changes the order of the
568 bits according to a~fixed permutation~$\pi$: The $i$-th element of the
569 resulting vector is equal to~$\alpha[\pi(i)]$.
571 Implemented as above, but with a~mask $y=(2^{\pi(b-1)},\ldots,2^{\pi(0)})$.
573 \:$\<Pack>(x)$ --- the inverse of \<Unpack>: given a~vector of zeroes and ones,
574 it produces a~number whose bits are the elements of the vector (in other words,
575 it crosses out the $\0^b$ blocks).
577 We interpret the~$x$ as an~encoding of a~vector with elements one bit shorter
578 and we sum these elements. For example, when $n=4$ and~$b=4$:
580 \setslot{\hbox{$x_3$}}
582 \def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
583 \def\.{\hphantom{\|}}
586 \|\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
587 \|\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
590 However, this ``reformatting'' does not produce a~correct encoding of a~vector,
591 because the separator zeroes are missing. For this reason, the implementation
592 of~\<Sum> using modulo does not work correctly (it produces $\0^b$ instead of $\1^b$).
593 We therefore use the technique based on multiplication instead, which does not need
594 the separators. (Alternatively, we can observe that $\1^b$ is the only case
595 affected, so we can handle it separately.)
600 We can use the aforementioned tricks to perform interesting operations on individual
601 numbers in constant time, too. Let us assume for a~while that we are
602 operating on $b$-bit numbers and the word size is at least~$b^2$.
603 This enables us to make use of intermediate vectors with $b$~elements
606 \algn{Integer operations in quadratic workspace}\id{lsbmsb}
610 \:$\<Weight>(\alpha)$ --- computes the Hamming weight of~$\alpha$, i.e., the number of ones in~$\(\alpha)$.
612 We perform \<Unpack> and then \<Sum>.
614 \:$\<Permute>_\pi(\alpha)$ --- shuffles the bits of~$\alpha$ according
615 to a~fixed permutation~$\pi$.
617 We perform $\<Unpack>_\pi$ and \<Pack> back.
619 \:$\<LSB>(\alpha)$ --- finds the least significant bit of~$\alpha$,
620 i.e., the smallest~$i$ such that $\alpha[i]=1$.
622 By a~combination of subtraction with $\bxor$, we create a~number
623 that contains ones exactly at the position of $\<LSB>(\alpha)$ and below:
626 \alpha&= \9\9\9\9\9\1\0\0\0\0\cr
627 \alpha-1&= \9\9\9\9\9\0\1\1\1\1\cr
628 \alpha\bxor(\alpha-1)&= \0\9\9\9\0\1\1\1\1\1\cr
631 Then we calculate the \<Weight> of the result and subtract~1.
633 \:$\<MSB>(\alpha)$ --- finds the most significant bit of~$\alpha$ (the position
634 of the highest bit set).
636 Reverse the bits of the number~$\alpha$ first by calling \<Permute>, then apply \<LSB>
637 and subtract the result from~$b-1$.
642 As noted by Brodnik~\cite{brodnik:lsb} and others, the space requirements of
643 the \<LSB> operation can be reduced to linear. We split the input to $\sqrt{b}$
644 blocks of $\sqrt{b}$ bits each. Then we determine which blocks are non-zero and
645 identify the lowest such block (this is a~\<LSB> of a~number whose bits
646 correspond to the blocks). Finally we calculate the \<LSB> of this block. In
647 both calls to \<LSB,> we have a $\sqrt{b}$-bit number in a~$b$-bit word, so we
648 can use the previous algorithm. The same trick of course works for finding the
651 The following algorithm shows the details.
653 \algn{LSB in linear workspace}
656 \algin A~$w$-bit number~$\alpha$.
657 \:$b\=\lceil\sqrt{w}\,\rceil$. \cmt{size of a~block}
658 \:$\ell\=b$. \cmt{the number of blocks is the same}
659 \:$x\=(\alpha \band (\0\1^b)^\ell) \bor (\alpha \band (\1\0^b)^\ell)$.
661 \cmt{encoding of a~vector~${\bf x}$ such that $x_i\ne 0$ iff the $i$-th block is non-zero}%
662 \foot{Why is this so complicated? It is tempting to take $\alpha$ itself as a~code of this vector,
663 but we unfortunately need the separator bits between elements, so we create them and
664 relocate the bits we have overwritten.}
665 \:$y\=\<Cmp>(0,x)$. \cmt{$y_i=1$ if the $i$-th block is non-zero, otherwise $y_0=0$}
666 \:$\beta\=\<Pack>(y)$. \cmt{each block compressed to a~single bit}
667 \:$p\=\<LSB>(\beta)$. \cmt{the index of the lowest non-zero block}
668 \:$\gamma\=(\alpha \shr bp) \band \1^b$. \cmt{the contents of that block}
669 \:$q\=\<LSB>(\gamma)$. \cmt{the lowest bit set there}
670 \algout $\<LSB>(\alpha) = bp+q$.
674 We have used a~plenty of constants that depend on the format of the vectors.
675 Either we can write non-uniform programs (see \ref{nonuniform}) and use native constants,
676 or we can observe that all such constants can be easily manufactured. For example,
677 $(\0^b\1)^d = \1^{(b+1)d} / \1^{b+1} = (2^{(b+1)d}-1)/(2^{b+1}-1)$. The only exceptions
678 are the~$w$ and~$b$ in the LSB algorithm \ref{lsb}, which we are unable to produce
679 in constant time. In practice we use the ``bit tricks'' as frequently called subroutines
680 in an~encompassing algorithm, so we usually can spend a~lot of time on the precalculation
681 of constants performed once during algorithm startup.
683 %--------------------------------------------------------------------------------
685 \section{Q-Heaps}\id{qheaps}%
687 We have shown how to perform non-trivial operations on a~set of values
688 in constant time, but so far only under the assumption that the number of these
689 values is small enough and that the values themselves are also small enough
690 (so that the whole set fits in $\O(1)$ machine words). Now we will show how to
691 lift the restriction on the magnitude of the values and still keep constant time
692 complexity. We will describe a~slightly simplified version of the Q-heaps developed by
693 Fredman and Willard in~\cite{fw:transdich}.
695 The Q-heap represents a~set of at most~$k$ word-sized integers, where $k\le W^{1/4}$
696 and $W$ is the word size of the machine. It will support insertion, deletion, finding
697 of minimum and maximum, and other operations described below, in constant time, provided that
698 we are willing to spend~$\O(2^{k^4})$ time on preprocessing.
700 The exponential-time preprocessing may sound alarming, but a~typical application uses
701 Q-heaps of size $k=\log^{1/4} N$, where $N$ is the size of the algorithm's input.
702 This guarantees that $k\le W^{1/4}$ and $\O(2^{k^4}) = \O(N)$. Let us however
703 remark that the whole construction is primarily of theoretical importance
704 and that the huge constants involved everywhere make these heaps useless
705 in practical algorithms. Many of the tricks used however prove themselves
706 useful even in real-life implementations.
708 Spending the time on reprocessing makes it possible to precompute tables for
709 almost arbitrary functions and then assume that they can be evaluated in
712 \lemma\id{qhprecomp}%
713 When~$f$ is a~function computable in polynomial time, $\O(2^{k^4})$ time is enough
714 to precompute a~table of the values of~$f$ for all arguments whose size is $\O(k^3)$ bits.
717 There are $2^{\O(k^3)}$ possible combinations of arguments of the given size and for each of
718 them we spend $\poly(k)$ time on calculating the function. It remains
719 to observe that $2^{\O(k^3)}\cdot \poly(k) = \O(2^{k^4})$.
723 We will first show an~auxiliary construction based on tries and then derive
724 the real definition of the Q-heap from it.
727 Let us introduce some notation first:
729 \:$W$ --- the word size of the RAM,
730 \:$k = \O(W^{1/4})$ --- the limit on the size of the heap,
731 \:$n\le k$ --- the number of elements stored in the heap,
732 \:$X=\{x_1, \ldots, x_n\}$ --- the elements themselves: distinct $W$-bit numbers
733 indexed in a~way that $x_1 < \ldots < x_n$,
734 \:$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,
735 \:$R_X(x)$ --- the rank of~$x$ in~$X$, that is the number of elements of~$X$ which are less than~$x$
736 (where $x$~itself need not be an~element of~$X$).\foot{We will dedicate the whole chapter \ref{rankchap} to the
737 study of various ranks.}
741 A~\df{trie} for a~set of strings~$S$ over a~finite alphabet~$\Sigma$ is
742 a~rooted tree whose vertices are the prefixes of the strings in~$S$ and there
743 is an~edge going from a~prefix~$\alpha$ to a~prefix~$\beta$ iff $\beta$ can be
744 obtained from~$\alpha$ by appending a~single symbol of the alphabet. The edge
745 will be labeled with the particular symbol. We will also define the~\df{letter depth}
746 of a~vertex as the length of the corresponding prefix. We mark the vertices
747 which match a~string of~$S$.
749 A~\df{compressed trie} is obtained from the trie by removing the vertices of outdegree~1
750 except for the root and marked vertices.
751 Whereever is a~directed path whose internal vertices have outdegree~1 and they carry
752 no mark, we replace this path by a~single edge labeled with the contatenation
753 of the original edge's labels.
755 In both kinds of tries, we order the outgoing edges of every vertex by their labels
759 In both tries, the root of the tree is the empty word and for every other vertex, the
760 corresponding prefix is equal to the concatenation of edge labels on the path
761 leading from the root to that vertex. The letter depth of the vertex is equal to
762 the total size of these labels. All leaves correspond to strings in~$S$, but so can
763 some internal vertices if there are two strings in~$S$ such that one is a~prefix
766 Furthermore, the labels of all edges leaving a~common vertex are always
767 distinct and when we compress the trie, no two such labels have share their initial
768 symbols. This allows us to search in the trie efficiently: when looking for
769 a~string~$x$, we follow the path from the root and whenever we visit
770 an~internal vertex of letter depth~$d$, we test the $d$-th character of~$x$,
771 we follow the edge whose label starts with this character, and we check that the
772 rest of the label matches.
774 The compressed trie is also efficient in terms of space consumption --- it has
775 $\O(\vert S\vert)$ vertices (this can be easily shown by induction on~$\vert S\vert$)
776 and all edge labels can be represented in space linear in the sum of the
777 lengths of the strings in~$S$.
780 For our set~$X$, we define~$T$ as a~compressed trie for the set of binary
781 encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W ; x\in X \}$.
784 The trie~$T$ has several interesting properties. Since all words in~$S$ have the same
785 length, the leaves of the trie correspond to these exact words, that is to the numbers~$x_i$.
786 The inorder traversal of the trie enumerates the words of~$S$ in lexicographic order
787 and therefore also the~$x_i$'s in the order of their values. Between each
788 pair of leaves $x_i$ and~$x_{i+1}$ it visits an~internal vertex whose letter depth
789 is exactly~$W-1-g_i$.
792 Let us now modify the algorithm for searching in the trie and make it compare
793 only the first symbols of the edges. In other words, we will test only the bits~$g_i$
794 which will be called \df{guides} (as they guide us through the tree). For $x\in
795 X$, the modified algorithm will still return the correct leaf. For all~$x$ outside~$X$
796 it will no longer fail and instead it will land on some leaf~$x_i$. At the
797 first sight the number~$x_i$ may seem unrelated, but we will show that it can be
798 used to determine the rank of~$x$ in~$X$, which will later form a~basis for all
802 The rank $R_X(x)$ is uniquely determined by a~combination of:
805 \:the index~$i$ of the leaf found when searching for~$x$ in~$T$,
806 \:the relation ($<$, $=$, $>$) between $x$ and $x_i$,
807 \:the bit position $b=\<MSB>(x\bxor x_i)$ of the first disagreement between~$x$ and~$x_i$.
811 If $x\in X$, we detect that from $x_i=x$ and the rank is obviously~$i-1$.
812 Let us assume that $x\not\in X$ and imagine that we follow the same path as when
814 but this time we check the full edge labels. The position~$b$ is the first position
815 where~$\(x)$ disagrees with a~label. Before this point, all edges not taken by
816 the search were leading either to subtrees containing elements all smaller than~$x$
817 or all larger than~$x$ and the only values not known yet are those in the subtree
818 below the edge that we currently consider. Now if $x[b]=0$ (and therefore $x<x_i$),
819 all values in that subtree have $x_j[b]=1$ and thus they are larger than~$x$. In the other
820 case, $x[b]=1$ and $x_j[b]=0$, so they are smaller.
824 The preceding lemma shows that the rank can be computed in polynomial time, but
825 unfortunately the variables on which it depends are too large for a~table to
826 be efficiently precomputed. We will carefully choose an~equivalent representation
827 of the trie which is compact enough.
830 The trie is uniquely determined by the order of the guides~$g_1,\ldots,g_{n-1}$.
833 We already know that the letter depths of the trie vertices are exactly
834 the numbers~$W-1-g_i$. The root of the trie must have the smallest of these
835 letter depths, i.e., it must correspond to the highest numbered bit. Let
836 us call this bit~$g_i$. This implies that the values $x_1,\ldots,x_i$
837 must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its
838 right subtree. Both subtrees can be then constructed recursively.\foot{This
839 construction is also known as the \df{cartesian tree} for the sequence
840 $g_1,\ldots,g_n$ and it is useful in many other algorithms as it can be
841 built in $\O(n)$ time. A~nice application on the Lowest Common Ancestor
842 and Range Minimum problems has been described by Bender et al.~in \cite{bender:lca}.}
846 Unfortunately, the vector of the $g_i$'s is also too long (is has $k\log W$ bits
847 and we have no upper bound on~$W$ in terms of~$k$), so we will compress it even
852 \:$B = \{g_1,\ldots,g_n\}$ --- the set of bit positions of all the guides, stored as a~sorted array,
853 \:$G : \{1,\ldots,n\} \rightarrow \{1,\ldots,n\}$ --- a~function mapping
854 the guides to their bit positions in~$B$: $g_i = B[G(i)]$,
855 \:$x[B]$ --- a~bit string containing the bits of~$x$ originally located
856 at the positions given by~$B$, i.e., the concatenation of bits $x[B[1]],
857 x[B[2]],\ldots, x[B[n]]$.
861 The set~$B$ has $\O(k\log W)=\O(W)$ bits, so it can be stored in a~constant number
862 of machine words in form of a~sorted vector. The function~$G$ can be also stored as a~vector
863 of $\O(k\log k)$ bits. We can change a~single~$g_i$ in constant time using
864 vector operations: First we delete the original value of~$g_i$ from~$B$ if it
865 is not used anywhere else. Then we add the new value to~$B$ if it was not
866 there yet and we write its position in~$B$ to~$G(i)$. Whenever we insert
867 or delete a~value in~$B$, the values at the higher positions shift one position
868 up or down and we have to update the pointers in~$G$. This can be fortunately
869 accomplished by adding or subtracting a~result of vector comparison.
871 In this representation, we can reformulate our lemma on ranks as follows:
874 The rank $R_X(x)$ can be computed in constant time from:
877 \:the values $x_1,\ldots,x_n$,
878 \:the bit string~$x[B]$,
883 Let us prove that all ingredients of Lemma~\ref{qhdeterm} are either small
884 enough or computable in constant time.
886 We know that the shape of the trie~$T$ is uniquely determined by the order of the $g_i$'s
887 and therefore by the function~$G$ since the array~$B$ is sorted. The shape of
888 the trie together with the bits in $x[B]$ determine the leaf~$x_i$ found when searching
889 for~$x$ using only the guides. This can be computed in polynomial time and it
890 depends on $\O(k\log k)$ bits of input, so according to Lemma~\ref{qhprecomp}
891 we can look it up in a~precomputed table.
893 The relation between $x$ and~$x_i$ can be obtained directly as we know the~$x_i$.
894 The bit position of the first disagreement can be calculated in constant time
895 using the LSB/MSB algorithm (\ref{lsb}).
897 All these ingredients can be stored in $\O(k\log k)$ bits, so we may assume
898 that the rank can be looked up in constant time as well.
902 In the Q-heap we would like to store the set~$X$ as a~sorted array together
903 with the corresponding trie, which will allow us to determine the position
904 for a~newly inserted element in constant time. However, the set is too large
905 to fit in a~vector and we cannot perform insertion on an~ordinary array in
906 constant time. This can be worked around by keeping the set in an~unsorted
907 array together with a~vector containing the permutation that sorts the array.
908 We can then insert a~new element at an~arbitrary place in the array and just
909 update the permutation to reflect the correct order.
911 We are now ready for the real definition of the Q-heap and for the description
912 of the basic operations on it.
915 A~\df{Q-heap} consists of:
917 \:$k$, $n$ --- the capacity of the heap and the current number of elements (word-sized integers),
918 \:$X$ --- the set of word-sized elements stored in the heap (an~array of words in an~arbitrary order),
919 \:$\varrho$ --- a~permutation on~$\{1,\ldots,n\}$ such that $X[\varrho(1)] < \ldots < X[\varrho(n)]$
920 (a~vector of $\O(n\log k)$ bits; we will write $x_i$ for $X[\varrho(i)]$),
921 \:$B$ --- a~set of ``interesting'' bit positions
922 (a~sorted vector of~$\O(n\log W)$ bits),
923 \:$G$ --- the function that maps the guides to the bit positions in~$B$
924 (a~vector of~$\O(n\log k)$ bits),
925 \:precomputed tables of various functions.
928 \algn{Search in the Q-heap}\id{qhfirst}%
930 \algin A~Q-heap and an~integer~$x$ to search for.
931 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
932 \:If $i\le n$ return $x_i$, otherwise return {\sc undefined.}
933 \algout The smallest element of the heap which is greater or equal to~$x$.
936 \algn{Insertion to the Q-heap}
938 \algin A~Q-heap and an~integer~$x$ to insert.
939 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
940 \:If $x=x_i$, return immediately (the value is already present).
941 \:Insert the new value to~$X$:
944 \::Insert~$n$ at the $i$-th position in the permutation~$\varrho$.
945 \:Update the $g_j$'s:
946 \::Move all~$g_j$ for $j\ge i$ one position up. \hfil\break
947 This translates to insertion in the vector representing~$G$.
948 \::Recalculate $g_{i-1}$ and~$g_i$ according to the definition.
949 \hfil\break Update~$B$ and~$G$ as described in~\ref{qhsetb}.
950 \algout The updated Q-heap.
953 \algn{Deletion from the Q-heap}
955 \algin A~Q-heap and an~integer~$x$ to be deleted from it.
956 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
957 \:If $i>n$ or $x_i\ne x$, return immediately (the value is not in the heap).
958 \:Delete the value from~$X$:
959 \::$X[\varrho(i)]\=X[n]$.
960 \::Find $j$ such that~$\varrho(j)=n$ and set $\varrho(j)\=\varrho(i)$.
962 \:Update the $g_j$'s like in the previous algorithm.
963 \algout The updated Q-heap.
966 \algn{Finding the $i$-th smallest element in the Q-heap}\id{qhlast}%
968 \algin A~Q-heap and an~index~$i$.
969 \:If $i<1$ or $i>n$, return {\sc undefined.}
971 \algout The $i$-th smallest element in the heap.
975 The heap algorithms we have just described have been built from primitives
976 operating in constant time, with one notable exception: the extraction
977 $x[B]$ of all bits of~$x$ at positions specified by the set~$B$. This cannot be done
978 in~$\O(1)$ time on the Word-RAM, but we can implement it with ${\rm AC}^0$
979 instructions as suggested by Andersson in \cite{andersson:fusion} or even
980 with those ${\rm AC}^0$ instructions present on real processors (see Thorup
981 \cite{thorup:aczero}). On the Word-RAM, we need to make use of the fact
982 that the set~$B$ is not changing too much --- there are $\O(1)$ changes
983 per Q-heap operation. As Fredman and Willard have shown, it is possible
984 to maintain a~``decoder'', whose state is stored in $\O(1)$ machine words,
985 and which helps us to extract $x[B]$ in a~constant number of operations:
987 \lemman{Extraction of bits}\id{qhxtract}%
988 Under the assumptions on~$k$, $W$ and the preprocessing time as in the Q-heaps,\foot{%
989 Actually, this is the only place where we need~$k$ to be as low as $W^{1/4}$.
990 In the ${\rm AC}^0$ implementation, it is enough to ensure $k\log k\le W$.
991 On the other hand, we need not care about the exponent because it can
992 be arbitrarily increased using the Q-heap trees described below.}
993 it is possible to maintain a~data structure for a~set~$B$ of bit positions,
994 which allows~$x[B]$ to be extracted in $\O(1)$ time for an~arbitrary~$x$.
995 When a~single element is inserted to~$B$ or deleted from~$B$, the structure
996 can be updated in constant time, as long as $\vert B\vert \le k$.
999 See Fredman and Willard \cite{fw:transdich}.
1003 This was the last missing bit of the mechanics of the Q-heaps. We are
1004 therefore ready to conclude this section by the following theorem
1005 and its consequences:
1007 \thmn{Q-heaps, Fredman and Willard \cite{fw:transdich}}\id{qh}%
1008 Let $W$ and~$k$ be positive integers such that $k=\O(W^{1/4})$. Let~$Q$
1009 be a~Q-heap of at most $k$-elements of $W$~bits each. Then the Q-heap
1010 operations \ref{qhfirst} to \ref{qhlast} on~$Q$ (insertion, deletion,
1011 search for a~given value and search for the $i$-th smallest element)
1012 run in constant time on a~Word-RAM with word size~$W$, after spending
1013 time $\O(2^{k^4})$ on the same RAM on precomputing of tables.
1016 Every operation on the Q-heap can be performed in a~constant number of
1017 vector operations and calculations of ranks. The ranks are computed
1018 in $\O(1)$ steps involving again $\O(1)$ vector operations, binary
1019 logarithms and bit extraction. All these can be calculated in constant
1020 time using the results of section \ref{bitsect} and Lemma \ref{qhxtract}.
1024 We can also use the Q-heaps as building blocks of more complex structures
1025 like Atomic heaps and AF-heaps (see once again \cite{fw:transdich}). We will
1026 show a~simpler, but useful construction, sometimes called the \df{Q-heap tree.}
1027 Suppose we have a~Q-heap of capacity~$k$ and a~parameter $d\in{\bb N}^+$. We
1028 can build a~balanced $k$-ary tree of depth~$d$ such that its leaves contain
1029 a~given set and every internal vertex keeps the minimum value in the subtree
1030 rooted in it, together with a~Q-heap containing the values in all its sons.
1031 This allows minimum to be extracted in constant time (it is placed in the root)
1032 and when any element is changed, it is sufficient to recalculate the values
1033 from the path from this element to the root, which takes $\O(d)$ Q-heap
1036 \corn{Q-heap trees}\id{qhtree}%
1037 For every positive integer~$r$ and $\delta>0$ there exists a~data structure
1038 capable of maintaining the minimum of a~set of at most~$r$ word-sized numbers
1039 under insertions and deletions. Each operation takes $\O(1)$ time on a~Word-RAM
1040 with word size $W=\Omega(r^{\delta})$, after spending time
1041 $\O(2^{r^\delta})$ on precomputing of tables.
1044 Choose $\delta' \le \delta$ such that $r^{\delta'} = \O(W^{1/4})$. Build
1045 a~Q-heap tree of depth $d=\lceil \delta/\delta'\rceil$ containing Q-heaps of
1046 size $k=r^{\delta'}$. \qed
1049 When we have an~algorithm with input of size~$N$, the word size is at least~$\log N$
1050 and we can spend time $\O(N)$ on preprocessing, so we can choose $r=\log N$ and
1051 $\delta=1$ in the above corollary and get a~heap of size $\log N$ working in
1052 constant time per operation.