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 equivalence 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 will denote their number of~$n_d$. We take
325 a~root of every such tree and label it with an~ordered $k$-tuple of identifiers
326 of its subtrees; when it has less than $k$ sons, we pad the tuple with empty
327 subtrees. Tuples corresponding to isomorphic subtrees are identical up to
328 reordering of elements. We therefore sort the codes inside each tuple and then
329 sort the tuples, which brings the equivalent tuples together.
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 To work around this, we sort 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$, ignoring the original positions. The second
336 sort is a~straightforward $k$-pass bucket sort.
338 If we are not careful, a~single sorting pass takes $\O(n_d + n)$ time, because
339 while we have only $n_d$~items to sort, we have to scan all $n$~buckets. This can
340 be easily avoided if we realize that the order of buckets does not need to be
341 fixed --- in every pass, we can use a~completely different order and it still
342 does bring the equivalent tuples together. Thus we can keep a~list of buckets
343 which were used in the current pass and look only inside these buckets. This way,
344 the pass takes $\O(n_d)$ time only and the whole algorithm is $\O(\sum_d n_d) = \O(n)$.
346 Our algorithm can be easily modified for trees with unrestricted degrees.
347 We replace the fixed $d$-tuples by general sequences of identifiers. The first
348 sort does not need any changes. In the second sort, we proceed from the first
349 position to the last one and after each bucket sort pass we put aside the sequences
350 that have just ended. (They are obviously not equivalent to any other sequences.)
351 The second sort is linear in the sum of the lengths of the sequences, which is
352 $n_{d+1}$ for depth~$d$. We can therefore decide isomorphism of the whole trees
353 in time $\O(\sum_d n_d + n_{d+1}) = \O(n)$.
356 The first linear-time algorithm that partitions all subtrees to isomorphism equivalence
357 classes is probably due to Zemlayachenko \cite{zemlay:treeiso}, but it lacks many
358 details. Dinitz et al.~\cite{dinitz:treeiso} have recast this algorithm in modern
359 terminology and filled the gaps. Our algorithm is easier to formulate than those,
360 because it replaces the need for auxiliary data structures by more elaborate bucket
363 \FIXME{Buchsbaum's trick}
365 %--------------------------------------------------------------------------------
367 \section{Data structures on the RAM}
370 There is a~lot of data structures designed specifically for the RAM, taking
371 advantage of both indexing and arithmetics. In many cases, they surpass the known
372 lower bounds for the same problem on the~PM and they often achieve constant time
373 per operation, at least when either the magnitude of the values or the size of
374 the data structure are suitably bounded.
376 A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt},
377 which represent a~subset of the integers $\{0,\ldots,U-1\}$, allowing insertion,
378 deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$,
379 regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's
380 algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm
381 for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$,
382 where $w_{max}$ is the maximum weight. We will show later that it is even
383 possible to achieve linear time complexity for arbitrary integer weights.
385 A~real breakthrough has been made by Fredman and Willard, who introduced
386 the Fusion trees~\cite{fw:fusion} which again perform membership and predecessor
387 operation on a~set of $n$~integers, but this time with complexity $\O(\log_W n)$
388 per operation on a~Word-RAM with $W$-bit words. This of course assumes that
389 each element of the set fits in a~single word. As $W$ must at least~$\log n$,
390 the operations take $\O(\log n/\log\log n)$ and we are able to sort $n$~integers
391 in time~$o(n\log n)$. This was a~beginning of a~long sequence of faster and
392 faster sorting algorithms, culminating with the work by Thorup and Han.
393 They have improved the time complexity of integer sorting to $\O(n\log\log n)$ deterministically~\cite{han:detsort}
394 and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:randsort},
395 both in linear space.
397 Despite the recent progress, the corner-stone of most RAM data structures
398 is still the representation of data structures by integers introduced by Fredman
399 and Willard. It will also form a~basis for the rest of this chapter.
401 \FIXME{Add more history.}
403 %--------------------------------------------------------------------------------
405 \section{Bits and vectors}\id{bitsect}
407 In this rather technical section, we will show how the RAM can be used as a~vector
408 computer to operate in parallel on multiple elements, as long as these elements
409 fit in a~single machine word. At the first sight this might seem useless, because we
410 cannot require large word sizes, but surprisingly often the elements are small
411 enough relative to the size of the algorithm's input and thus also relative to
412 the minimum possible word size. Also, as the following lemma shows, we can
413 easily emulate slightly longer words:
415 \lemman{Multiple-precision calculations}
416 Given a~RAM with $W$-bit words, we can emulate all calculation and control
417 instructions of a~RAM with word size $kW$ in time depending only on the~$k$.
418 (This is usually called \df{multiple-precision arithmetics.})
421 We split each word of the ``big'' machine to $W'$-bit blocks, where $W'=W/2$, and store these
422 blocks in $2k$ consecutive memory cells. Addition, subtraction, comparison and
423 bitwise logical operations can be performed block-by-block. Shifts by a~multiple
424 of~$W'$ are trivial, otherwise we can combine each block of the result from
425 shifted versions of two original blocks.
426 To multiply two numbers, we can use the elementary school algorithm using the $W'$-bit
427 blocks as digits in base $2^{W'}$ --- the product of any two blocks fits
430 Division is harder, but Newton-Raphson iteration (see~\cite{ito:newrap})
431 converges to the quotient in a~constant number of iterations, each of them
432 involving $\O(1)$ multiple-precision additions and multiplications. A~good
433 starting approximation can be obtained by dividing the two most-significant
434 (non-zero) blocks of both numbers.
436 Another approach to division is using the improved elementary school algorithm as described
437 by Knuth in~\cite{knuth:seminalg}. It uses $\O(k^2)$ steps, but the steps involve
438 calculation of the most significant bit set in a~word. We will show below that it
439 can be done in constant time, but we have to be careful to avoid division instructions.
442 \notan{Bit strings}\id{bitnota}%
443 We will work with binary representations of natural numbers by strings over the
444 alphabet $\{\0,\1\}$: we will use $\(x)$ for the number~$x$ written in binary,
445 $\(x)_b$ for the same padded to exactly $b$ bits by adding leading zeroes,
446 and $x[k]$ for the value of the $k$-th bit of~$x$ (with a~numbering of bits such that $2^k[k]=1$).
447 The usual conventions for operations on strings will be utilized: When $s$
448 and~$t$ are strings, we write $st$ for their concatenation and
449 $s^k$ for the string~$s$ repeated $k$~times.
450 When the meaning is clear from the context,
451 we will use $x$ and $\(x)$ interchangeably to avoid outbreak of symbols.
454 The \df{bitwise encoding} of a~vector ${\bf x}=(x_0,\ldots,x_{d-1})$ of~$b$-bit numbers
455 is an~integer~$x$ such that $\(x)=\(x_{d-1})_b\0\(x_{d-2})_b\0\ldots\0\(x_0)_b$, i.e.,
456 $x = \sum_i 2^{(b+1)i}\cdot x_i$. (We have interspersed the elements with \df{separator bits.})
458 \notan{Vectors}\id{vecnota}%
459 We will use boldface letters for vectors and the same letters in normal type
460 for their encodings. The elements of a~vector~${\bf x}$ will be written as
461 $x_0,\ldots,x_{d-1}$.
464 If we want to fit the whole vector in a~single word, the parameters $b$ and~$d$ must satisty
465 the condition $(b+1)d\le W$.
466 By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
467 We will now describe how to translate simple vector manipulations to sequences of $\O(1)$ RAM operations
468 on their codes. As we are interested in asymptotic complexity only, we prefer clarity
469 of the algorithms over saving instructions. Among other things, we freely use calculations
470 on words of size $\O(bd)$, assuming that the Multiple-precision lemma comes to save us
474 First of all, let us observe that we can use $\band$ and $\bor$ with suitable constants
475 to write zeroes or ones to an~arbitrary set of bit positions at once. These operations
476 are usually called \df{bit masking}. Also, any element of a~vector can be extracted or
477 replaced by a~different value in $\O(1)$ time by masking and shifts.
480 \def\setslot#1{\setbox0=#1\slotwd=\wd0}
481 \def\slot#1{\hbox to \slotwd{\hfil #1\hfil}}
482 \def\[#1]{\slot{$#1$}}
483 \def\9{\rack{\0}{\hss$\cdot$\hss}}
487 \halign{\hskip 0.15\hsize\hfil $ ##$&\hbox to 0.6\hsize{${}##$ \hss}\cr
492 \algn{Operations on vectors with $d$~elements of $b$~bits each}\id{vecops}
496 \:$\<Replicate>(\alpha)$ --- creates a~vector $(\alpha,\ldots,\alpha)$:
498 \alik{\<Replicate>(\alpha)=\alpha\cdot(\0^b\1)^d. \cr}
500 \:$\<Sum>(x)$ --- calculates the sum of the elements of~${\bf x}$, assuming that
501 the result fits in $b$~bits:
503 \alik{\<Sum>(x) = x \bmod \1^{b+1}. \cr}
505 This is correct because when we calculate modulo~$\1^{b+1}$, the number $2^{b+1}=\1\0^{b+1}$
506 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$.
507 As the result should fit in $b$~bits, the modulo makes no difference.
509 If we want to avoid division, we can use double-precision multiplication instead:
511 \setslot{\hbox{~$\0x_{d-1}$}}
514 \def\dd{\slot{$\cdots$}}
515 \def\vd{\slot{$\vdots$}}
516 \def\rule{\noalign{\medskip\nointerlineskip}$\hrulefill$\cr\noalign{\nointerlineskip\medskip}}
519 \[\0x_{d-1}] \dd \[\0x_2] \[\0x_1] \[\0x_0] \cr
520 *~~ \z \dd \z\z\z \cr
522 \[x_{d-1}] \dd \[x_2] \[x_1] \[x_0] \cr
523 \[x_{d-1}] \[x_{d-2}] \dd \[x_1] \[x_0] \. \cr
524 \[x_{d-1}] \[x_{d-2}] \[x_{d-3}] \dd \[x_0] \. \. \cr
525 \vd\vd\vd\vd\.\.\.\cr
526 \[x_{d-1}] \dd \[x_2]\[x_1]\[x_0] \. \. \. \. \cr
528 \[r_{d-1}] \dd \[r_2] \[r_1] \[s_d] \dd \[s_3] \[s_2] \[s_1] \cr
531 This way, we even get the vector of all partial sums:
532 $s_k=\sum_{i=0}^{k-1}x_i$, $r_k=\sum_{i=k}^{d-1}x_i$.
534 \:$\<Cmp>(x,y)$ --- element-wise comparison of~vectors ${\bf x}$ and~${\bf y}$,
535 i.e., a~vector ${\bf z}$ such that $z_i=1$ if $x_i<y_i$ and $z_i=0$ otherwise.
537 We replace the separator zeroes in~$x$ by ones and subtract~$y$. These ones
538 change back to zeroes exactly at the positions where $x_i<y_i$ and they stop
539 carries from propagating, so the fields do not interact with each other:
541 \setslot{\vbox{\hbox{~$x_{d-1}$}\hbox{~$y_{d-1}$}}}
542 \def\9{\rack{\0}{\hss ?\hss}}
544 \1 \[x_{d-1}] \1 \[x_{d-2}] \[\cdots] \1 \[x_1] \1 \[x_0] \cr
545 -~ \0 \[y_{d-1}] \0 \[y_{d-2}] \[\cdots] \0 \[y_1] \0 \[y_0] \cr
547 \9 \[\ldots] \9 \[\ldots] \[\cdots] \9 \[\ldots] \9 \[\ldots] \cr
550 It only remains to shift the separator bits to the right positions, negate them
551 and mask out all other bits.
553 \:$\<Rank>(x,\alpha)$ --- returns the number of elements of~${\bf x}$ which are less than~$\alpha$,
554 assuming that the result fits in~$b$ bits:
557 \<Rank>(x,\alpha) = \<Sum>(\<Cmp>(x,\<Replicate>(\alpha))). \cr
560 \:$\<Insert>(x,\alpha)$ --- inserts~$\alpha$ into a~sorted vector $\bf x$:
562 We calculate the rank of~$\alpha$ in~$x$ first, then we insert~$\alpha$ as the $k$-th
563 field of~$\bf x$ using masking operations and shifts.
566 \:$k\=\<Rank>(x,\alpha)$.
567 \:$\ell\=x \band \1^{(b+1)(n-k-1)}\0^{(b+1)(k+1)}$. \cmt{``left'' part of the vector}
568 \:$r=x \band \1^{(b+1)k}$. \cmt{``right'' part}
569 \:Return $(\ell\shl (b+1)) \bor (\alpha\shl ((b+1)k)) \bor r$.
572 \:$\<Unpack>(\alpha)$ --- creates a~vector whose elements are the bits of~$\(\alpha)_d$.
573 In other words, inserts blocks~$\0^b$ between the bits of~$\alpha$. Assuming that $b\ge d$,
574 we can do it as follows:
577 \:$x\=\<Replicate>(\alpha)$.
578 \:$y\=(2^{b-1},2^{b-2},\ldots,2^0)$. \cmt{bitwise encoding of this vector}
580 \:Return $\<Cmp>(z,y)$.
583 Let us observe that $z_i$ is either zero or equal to~$y_i$ depending on the value
584 of the $i$-th bit of the number~$\alpha$. Comparing it with~$y_i$ normalizes it
585 to either zero or one.
587 \:$\<Unpack>_\pi(\alpha)$ --- like \<Unpack>, but changes the order of the
588 bits according to a~fixed permutation~$\pi$: The $i$-th element of the
589 resulting vector is equal to~$\alpha[\pi(i)]$.
591 Implemented as above, but with a~mask $y=(2^{\pi(b-1)},\ldots,2^{\pi(0)})$.
593 \:$\<Pack>(x)$ --- the inverse of \<Unpack>: given a~vector of zeroes and ones,
594 it produces a~number whose bits are the elements of the vector (in other words,
595 it crosses out the $\0^b$ blocks).
597 We interpret the~$x$ as an~encoding of a~vector with elements one bit shorter
598 and we sum these elements. For example, when $n=4$ and~$b=4$:
600 \setslot{\hbox{$x_3$}}
602 \def\|{\hskip1pt\vrule height 10pt depth 4pt\hskip1pt}
603 \def\.{\hphantom{\|}}
606 \|\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
607 \|\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
610 However, this ``reformatting'' does not produce a~correct encoding of a~vector,
611 because the separator zeroes are missing. For this reason, the implementation
612 of~\<Sum> using modulo does not work correctly (it produces $\0^b$ instead of $\1^b$).
613 We therefore use the technique based on multiplication instead, which does not need
614 the separators. (Alternatively, we can observe that $\1^b$ is the only case
615 affected, so we can handle it separately.)
620 We can use the aforementioned tricks to perform interesting operations on individual
621 numbers in constant time, too. Let us assume for a~while that we are
622 operating on $b$-bit numbers and the word size is at least~$b^2$.
623 This enables us to make use of intermediate vectors with $b$~elements
626 \algn{Integer operations in quadratic workspace}\id{lsbmsb}
630 \:$\<Weight>(\alpha)$ --- computes the Hamming weight of~$\alpha$, i.e., the number of ones in~$\(\alpha)$.
632 We perform \<Unpack> and then \<Sum>.
634 \:$\<Permute>_\pi(\alpha)$ --- shuffles the bits of~$\alpha$ according
635 to a~fixed permutation~$\pi$.
637 We perform $\<Unpack>_\pi$ and \<Pack> back.
639 \:$\<LSB>(\alpha)$ --- finds the least significant bit of~$\alpha$,
640 i.e., the smallest~$i$ such that $\alpha[i]=1$.
642 By a~combination of subtraction with $\bxor$, we create a~number
643 that contains ones exactly at the position of $\<LSB>(\alpha)$ and below:
646 \alpha&= \9\9\9\9\9\1\0\0\0\0\cr
647 \alpha-1&= \9\9\9\9\9\0\1\1\1\1\cr
648 \alpha\bxor(\alpha-1)&= \0\9\9\9\0\1\1\1\1\1\cr
651 Then we calculate the \<Weight> of the result and subtract~1.
653 \:$\<MSB>(\alpha)$ --- finds the most significant bit of~$\alpha$ (the position
654 of the highest bit set).
656 Reverse the bits of the number~$\alpha$ first by calling \<Permute>, then apply \<LSB>
657 and subtract the result from~$b-1$.
662 As noted by Brodnik~\cite{brodnik:lsb} and others, the space requirements of
663 the \<LSB> operation can be reduced to linear. We split the input to $\sqrt{b}$
664 blocks of $\sqrt{b}$ bits each. Then we determine which blocks are non-zero and
665 identify the lowest such block (this is a~\<LSB> of a~number whose bits
666 correspond to the blocks). Finally we calculate the \<LSB> of this block. In
667 both calls to \<LSB,> we have a $\sqrt{b}$-bit number in a~$b$-bit word, so we
668 can use the previous algorithm. The same trick of course works for finding the
671 The following algorithm shows the details.
673 \algn{LSB in linear workspace}
676 \algin A~$w$-bit number~$\alpha$.
677 \:$b\=\lceil\sqrt{w}\,\rceil$. \cmt{size of a~block}
678 \:$\ell\=b$. \cmt{the number of blocks is the same}
679 \:$x\=(\alpha \band (\0\1^b)^\ell) \bor (\alpha \band (\1\0^b)^\ell)$.
681 \cmt{encoding of a~vector~${\bf x}$ such that $x_i\ne 0$ iff the $i$-th block is non-zero}%
682 \foot{Why is this so complicated? It is tempting to take $\alpha$ itself as a~code of this vector,
683 but we unfortunately need the separator bits between elements, so we create them and
684 relocate the bits we have overwritten.}
685 \:$y\=\<Cmp>(0,x)$. \cmt{$y_i=1$ if the $i$-th block is non-zero, otherwise $y_0=0$}
686 \:$\beta\=\<Pack>(y)$. \cmt{each block compressed to a~single bit}
687 \:$p\=\<LSB>(\beta)$. \cmt{the index of the lowest non-zero block}
688 \:$\gamma\=(\alpha \shr bp) \band \1^b$. \cmt{the contents of that block}
689 \:$q\=\<LSB>(\gamma)$. \cmt{the lowest bit set there}
690 \algout $\<LSB>(\alpha) = bp+q$.
694 We have used a~plenty of constants that depend on the format of the vectors.
695 Either we can write non-uniform programs (see \ref{nonuniform}) and use native constants,
696 or we can observe that all such constants can be easily manufactured. For example,
697 $(\0^b\1)^d = \1^{(b+1)d} / \1^{b+1} = (2^{(b+1)d}-1)/(2^{b+1}-1)$. The only exceptions
698 are the~$w$ and~$b$ in the LSB algorithm \ref{lsb}, which we are unable to produce
699 in constant time. In practice we use the ``bit tricks'' as frequently called subroutines
700 in an~encompassing algorithm, so we usually can spend a~lot of time on the precalculation
701 of constants performed once during algorithm startup.
703 %--------------------------------------------------------------------------------
705 \section{Q-Heaps}\id{qheaps}%
707 We have shown how to perform non-trivial operations on a~set of values
708 in constant time, but so far only under the assumption that the number of these
709 values is small enough and that the values themselves are also small enough
710 (so that the whole set fits in $\O(1)$ machine words). Now we will show how to
711 lift the restriction on the magnitude of the values and still keep constant time
712 complexity. We will describe a~slightly simplified version of the Q-heaps developed by
713 Fredman and Willard in~\cite{fw:transdich}.
715 The Q-heap represents a~set of at most~$k$ word-sized integers, where $k\le W^{1/4}$
716 and $W$ is the word size of the machine. It will support insertion, deletion, finding
717 of minimum and maximum, and other operations described below, in constant time, provided that
718 we are willing to spend~$\O(2^{k^4})$ time on preprocessing.
720 The exponential-time preprocessing may sound alarming, but a~typical application uses
721 Q-heaps of size $k=\log^{1/4} N$, where $N$ is the size of the algorithm's input.
722 This guarantees that $k\le W^{1/4}$ and $\O(2^{k^4}) = \O(N)$. Let us however
723 remark that the whole construction is primarily of theoretical importance
724 and that the huge constants involved everywhere make these heaps useless
725 in practical algorithms. Many of the tricks used however prove themselves
726 useful even in real-life implementations.
728 Spending the time on reprocessing makes it possible to precompute tables for
729 almost arbitrary functions and then assume that they can be evaluated in
732 \lemma\id{qhprecomp}%
733 When~$f$ is a~function computable in polynomial time, $\O(2^{k^4})$ time is enough
734 to precompute a~table of the values of~$f$ for all arguments whose size is $\O(k^3)$ bits.
737 There are $2^{\O(k^3)}$ possible combinations of arguments of the given size and for each of
738 them we spend $\poly(k)$ time on calculating the function. It remains
739 to observe that $2^{\O(k^3)}\cdot \poly(k) = \O(2^{k^4})$.
743 We will first show an~auxiliary construction based on tries and then derive
744 the real definition of the Q-heap from it.
747 Let us introduce some notation first:
749 \:$W$ --- the word size of the RAM,
750 \:$k = \O(W^{1/4})$ --- the limit on the size of the heap,
751 \:$n\le k$ --- the number of elements stored in the heap,
752 \:$X=\{x_1, \ldots, x_n\}$ --- the elements themselves: distinct $W$-bit numbers
753 indexed in a~way that $x_1 < \ldots < x_n$,
754 \:$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,
755 \:$R_X(x)$ --- the rank of~$x$ in~$X$, that is the number of elements of~$X$ which are less than~$x$
756 (where $x$~itself need not be an~element of~$X$).\foot{We will dedicate the whole chapter \ref{rankchap} to the
757 study of various ranks.}
761 A~\df{trie} for a~set of strings~$S$ over a~finite alphabet~$\Sigma$ is
762 a~rooted tree whose vertices are the prefixes of the strings in~$S$ and there
763 is an~edge going from a~prefix~$\alpha$ to a~prefix~$\beta$ iff $\beta$ can be
764 obtained from~$\alpha$ by appending a~single symbol of the alphabet. The edge
765 will be labeled with the particular symbol. We will also define the~\df{letter depth}
766 of a~vertex as the length of the corresponding prefix. We mark the vertices
767 which match a~string of~$S$.
769 A~\df{compressed trie} is obtained from the trie by removing the vertices of outdegree~1
770 except for the root and marked vertices.
771 Whereever is a~directed path whose internal vertices have outdegree~1 and they carry
772 no mark, we replace this path by a~single edge labeled with the contatenation
773 of the original edge's labels.
775 In both kinds of tries, we order the outgoing edges of every vertex by their labels
779 In both tries, the root of the tree is the empty word and for every other vertex, the
780 corresponding prefix is equal to the concatenation of edge labels on the path
781 leading from the root to that vertex. The letter depth of the vertex is equal to
782 the total size of these labels. All leaves correspond to strings in~$S$, but so can
783 some internal vertices if there are two strings in~$S$ such that one is a~prefix
786 Furthermore, the labels of all edges leaving a~common vertex are always
787 distinct and when we compress the trie, no two such labels have share their initial
788 symbols. This allows us to search in the trie efficiently: when looking for
789 a~string~$x$, we follow the path from the root and whenever we visit
790 an~internal vertex of letter depth~$d$, we test the $d$-th character of~$x$,
791 we follow the edge whose label starts with this character, and we check that the
792 rest of the label matches.
794 The compressed trie is also efficient in terms of space consumption --- it has
795 $\O(\vert S\vert)$ vertices (this can be easily shown by induction on~$\vert S\vert$)
796 and all edge labels can be represented in space linear in the sum of the
797 lengths of the strings in~$S$.
800 For our set~$X$, we define~$T$ as a~compressed trie for the set of binary
801 encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W ; x\in X \}$.
804 The trie~$T$ has several interesting properties. Since all words in~$S$ have the same
805 length, the leaves of the trie correspond to these exact words, that is to the numbers~$x_i$.
806 The inorder traversal of the trie enumerates the words of~$S$ in lexicographic order
807 and therefore also the~$x_i$'s in the order of their values. Between each
808 pair of leaves $x_i$ and~$x_{i+1}$ it visits an~internal vertex whose letter depth
809 is exactly~$W-1-g_i$.
812 Let us now modify the algorithm for searching in the trie and make it compare
813 only the first symbols of the edges. In other words, we will test only the bits~$g_i$
814 which will be called \df{guides} (as they guide us through the tree). For $x\in
815 X$, the modified algorithm will still return the correct leaf. For all~$x$ outside~$X$
816 it will no longer fail and instead it will land on some leaf~$x_i$. At the
817 first sight the number~$x_i$ may seem unrelated, but we will show that it can be
818 used to determine the rank of~$x$ in~$X$, which will later form a~basis for all
822 The rank $R_X(x)$ is uniquely determined by a~combination of:
825 \:the index~$i$ of the leaf found when searching for~$x$ in~$T$,
826 \:the relation ($<$, $=$, $>$) between $x$ and $x_i$,
827 \:the bit position $b=\<MSB>(x\bxor x_i)$ of the first disagreement between~$x$ and~$x_i$.
831 If $x\in X$, we detect that from $x_i=x$ and the rank is obviously~$i-1$.
832 Let us assume that $x\not\in X$ and imagine that we follow the same path as when
834 but this time we check the full edge labels. The position~$b$ is the first position
835 where~$\(x)$ disagrees with a~label. Before this point, all edges not taken by
836 the search were leading either to subtrees containing elements all smaller than~$x$
837 or all larger than~$x$ and the only values not known yet are those in the subtree
838 below the edge that we currently consider. Now if $x[b]=0$ (and therefore $x<x_i$),
839 all values in that subtree have $x_j[b]=1$ and thus they are larger than~$x$. In the other
840 case, $x[b]=1$ and $x_j[b]=0$, so they are smaller.
844 The preceding lemma shows that the rank can be computed in polynomial time, but
845 unfortunately the variables on which it depends are too large for a~table to
846 be efficiently precomputed. We will carefully choose an~equivalent representation
847 of the trie which is compact enough.
850 The trie is uniquely determined by the order of the guides~$g_1,\ldots,g_{n-1}$.
853 We already know that the letter depths of the trie vertices are exactly
854 the numbers~$W-1-g_i$. The root of the trie must have the smallest of these
855 letter depths, i.e., it must correspond to the highest numbered bit. Let
856 us call this bit~$g_i$. This implies that the values $x_1,\ldots,x_i$
857 must lie in the left subtree of the root and $x_{i+1},\ldots,x_n$ in its
858 right subtree. Both subtrees can be then constructed recursively.\foot{This
859 construction is also known as the \df{cartesian tree} for the sequence
860 $g_1,\ldots,g_n$ and it is useful in many other algorithms as it can be
861 built in $\O(n)$ time. A~nice application on the Lowest Common Ancestor
862 and Range Minimum problems has been described by Bender et al.~in \cite{bender:lca}.}
866 Unfortunately, the vector of the $g_i$'s is also too long (is has $k\log W$ bits
867 and we have no upper bound on~$W$ in terms of~$k$), so we will compress it even
872 \:$B = \{g_1,\ldots,g_n\}$ --- the set of bit positions of all the guides, stored as a~sorted array,
873 \:$G : \{1,\ldots,n\} \rightarrow \{1,\ldots,n\}$ --- a~function mapping
874 the guides to their bit positions in~$B$: $g_i = B[G(i)]$,
875 \:$x[B]$ --- a~bit string containing the bits of~$x$ originally located
876 at the positions given by~$B$, i.e., the concatenation of bits $x[B[1]],
877 x[B[2]],\ldots, x[B[n]]$.
881 The set~$B$ has $\O(k\log W)=\O(W)$ bits, so it can be stored in a~constant number
882 of machine words in form of a~sorted vector. The function~$G$ can be also stored as a~vector
883 of $\O(k\log k)$ bits. We can change a~single~$g_i$ in constant time using
884 vector operations: First we delete the original value of~$g_i$ from~$B$ if it
885 is not used anywhere else. Then we add the new value to~$B$ if it was not
886 there yet and we write its position in~$B$ to~$G(i)$. Whenever we insert
887 or delete a~value in~$B$, the values at the higher positions shift one position
888 up or down and we have to update the pointers in~$G$. This can be fortunately
889 accomplished by adding or subtracting a~result of vector comparison.
891 In this representation, we can reformulate our lemma on ranks as follows:
894 The rank $R_X(x)$ can be computed in constant time from:
897 \:the values $x_1,\ldots,x_n$,
898 \:the bit string~$x[B]$,
903 Let us prove that all ingredients of Lemma~\ref{qhdeterm} are either small
904 enough or computable in constant time.
906 We know that the shape of the trie~$T$ is uniquely determined by the order of the $g_i$'s
907 and therefore by the function~$G$ since the array~$B$ is sorted. The shape of
908 the trie together with the bits in $x[B]$ determine the leaf~$x_i$ found when searching
909 for~$x$ using only the guides. This can be computed in polynomial time and it
910 depends on $\O(k\log k)$ bits of input, so according to Lemma~\ref{qhprecomp}
911 we can look it up in a~precomputed table.
913 The relation between $x$ and~$x_i$ can be obtained directly as we know the~$x_i$.
914 The bit position of the first disagreement can be calculated in constant time
915 using the LSB/MSB algorithm (\ref{lsb}).
917 All these ingredients can be stored in $\O(k\log k)$ bits, so we may assume
918 that the rank can be looked up in constant time as well.
922 In the Q-heap we would like to store the set~$X$ as a~sorted array together
923 with the corresponding trie, which will allow us to determine the position
924 for a~newly inserted element in constant time. However, the set is too large
925 to fit in a~vector and we cannot perform insertion on an~ordinary array in
926 constant time. This can be worked around by keeping the set in an~unsorted
927 array together with a~vector containing the permutation that sorts the array.
928 We can then insert a~new element at an~arbitrary place in the array and just
929 update the permutation to reflect the correct order.
931 We are now ready for the real definition of the Q-heap and for the description
932 of the basic operations on it.
935 A~\df{Q-heap} consists of:
937 \:$k$, $n$ --- the capacity of the heap and the current number of elements (word-sized integers),
938 \:$X$ --- the set of word-sized elements stored in the heap (an~array of words in an~arbitrary order),
939 \:$\varrho$ --- a~permutation on~$\{1,\ldots,n\}$ such that $X[\varrho(1)] < \ldots < X[\varrho(n)]$
940 (a~vector of $\O(n\log k)$ bits; we will write $x_i$ for $X[\varrho(i)]$),
941 \:$B$ --- a~set of ``interesting'' bit positions
942 (a~sorted vector of~$\O(n\log W)$ bits),
943 \:$G$ --- the function that maps the guides to the bit positions in~$B$
944 (a~vector of~$\O(n\log k)$ bits),
945 \:precomputed tables of various functions.
948 \algn{Search in the Q-heap}\id{qhfirst}%
950 \algin A~Q-heap and an~integer~$x$ to search for.
951 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
952 \:If $i\le n$ return $x_i$, otherwise return {\sc undefined.}
953 \algout The smallest element of the heap which is greater or equal to~$x$.
956 \algn{Insertion to the Q-heap}
958 \algin A~Q-heap and an~integer~$x$ to insert.
959 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
960 \:If $x=x_i$, return immediately (the value is already present).
961 \:Insert the new value to~$X$:
964 \::Insert~$n$ at the $i$-th position in the permutation~$\varrho$.
965 \:Update the $g_j$'s:
966 \::Move all~$g_j$ for $j\ge i$ one position up. \hfil\break
967 This translates to insertion in the vector representing~$G$.
968 \::Recalculate $g_{i-1}$ and~$g_i$ according to the definition.
969 \hfil\break Update~$B$ and~$G$ as described in~\ref{qhsetb}.
970 \algout The updated Q-heap.
973 \algn{Deletion from the Q-heap}
975 \algin A~Q-heap and an~integer~$x$ to be deleted from it.
976 \:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
977 \:If $i>n$ or $x_i\ne x$, return immediately (the value is not in the heap).
978 \:Delete the value from~$X$:
979 \::$X[\varrho(i)]\=X[n]$.
980 \::Find $j$ such that~$\varrho(j)=n$ and set $\varrho(j)\=\varrho(i)$.
982 \:Update the $g_j$'s like in the previous algorithm.
983 \algout The updated Q-heap.
986 \algn{Finding the $i$-th smallest element in the Q-heap}\id{qhlast}%
988 \algin A~Q-heap and an~index~$i$.
989 \:If $i<1$ or $i>n$, return {\sc undefined.}
991 \algout The $i$-th smallest element in the heap.
995 The heap algorithms we have just described have been built from primitives
996 operating in constant time, with one notable exception: the extraction
997 $x[B]$ of all bits of~$x$ at positions specified by the set~$B$. This cannot be done
998 in~$\O(1)$ time on the Word-RAM, but we can implement it with ${\rm AC}^0$
999 instructions as suggested by Andersson in \cite{andersson:fusion} or even
1000 with those ${\rm AC}^0$ instructions present on real processors (see Thorup
1001 \cite{thorup:aczero}). On the Word-RAM, we need to make use of the fact
1002 that the set~$B$ is not changing too much --- there are $\O(1)$ changes
1003 per Q-heap operation. As Fredman and Willard have shown, it is possible
1004 to maintain a~``decoder'', whose state is stored in $\O(1)$ machine words,
1005 and which helps us to extract $x[B]$ in a~constant number of operations:
1007 \lemman{Extraction of bits}\id{qhxtract}%
1008 Under the assumptions on~$k$, $W$ and the preprocessing time as in the Q-heaps,\foot{%
1009 Actually, this is the only place where we need~$k$ to be as low as $W^{1/4}$.
1010 In the ${\rm AC}^0$ implementation, it is enough to ensure $k\log k\le W$.
1011 On the other hand, we need not care about the exponent because it can
1012 be arbitrarily increased using the Q-heap trees described below.}
1013 it is possible to maintain a~data structure for a~set~$B$ of bit positions,
1014 which allows~$x[B]$ to be extracted in $\O(1)$ time for an~arbitrary~$x$.
1015 When a~single element is inserted to~$B$ or deleted from~$B$, the structure
1016 can be updated in constant time, as long as $\vert B\vert \le k$.
1019 See Fredman and Willard \cite{fw:transdich}.
1023 This was the last missing bit of the mechanics of the Q-heaps. We are
1024 therefore ready to conclude this section by the following theorem
1025 and its consequences:
1027 \thmn{Q-heaps, Fredman and Willard \cite{fw:transdich}}\id{qh}%
1028 Let $W$ and~$k$ be positive integers such that $k=\O(W^{1/4})$. Let~$Q$
1029 be a~Q-heap of at most $k$-elements of $W$~bits each. Then the Q-heap
1030 operations \ref{qhfirst} to \ref{qhlast} on~$Q$ (insertion, deletion,
1031 search for a~given value and search for the $i$-th smallest element)
1032 run in constant time on a~Word-RAM with word size~$W$, after spending
1033 time $\O(2^{k^4})$ on the same RAM on precomputing of tables.
1036 Every operation on the Q-heap can be performed in a~constant number of
1037 vector operations and calculations of ranks. The ranks are computed
1038 in $\O(1)$ steps involving again $\O(1)$ vector operations, binary
1039 logarithms and bit extraction. All these can be calculated in constant
1040 time using the results of section \ref{bitsect} and Lemma \ref{qhxtract}.
1044 We can also use the Q-heaps as building blocks of more complex structures
1045 like Atomic heaps and AF-heaps (see once again \cite{fw:transdich}). We will
1046 show a~simpler, but useful construction, sometimes called the \df{Q-heap tree.}
1047 Suppose we have a~Q-heap of capacity~$k$ and a~parameter $d\in{\bb N}^+$. We
1048 can build a~balanced $k$-ary tree of depth~$d$ such that its leaves contain
1049 a~given set and every internal vertex keeps the minimum value in the subtree
1050 rooted in it, together with a~Q-heap containing the values in all its sons.
1051 This allows minimum to be extracted in constant time (it is placed in the root)
1052 and when any element is changed, it is sufficient to recalculate the values
1053 from the path from this element to the root, which takes $\O(d)$ Q-heap
1056 \corn{Q-heap trees}\id{qhtree}%
1057 For every positive integer~$r$ and $\delta>0$ there exists a~data structure
1058 capable of maintaining the minimum of a~set of at most~$r$ word-sized numbers
1059 under insertions and deletions. Each operation takes $\O(1)$ time on a~Word-RAM
1060 with word size $W=\Omega(r^{\delta})$, after spending time
1061 $\O(2^{r^\delta})$ on precomputing of tables.
1064 Choose $\delta' \le \delta$ such that $r^{\delta'} = \O(W^{1/4})$. Build
1065 a~Q-heap tree of depth $d=\lceil \delta/\delta'\rceil$ containing Q-heaps of
1066 size $k=r^{\delta'}$. \qed
1069 When we have an~algorithm with input of size~$N$, the word size is at least~$\log N$
1070 and we can spend time $\O(N)$ on preprocessing, so we can choose $r=\log N$ and
1071 $\delta=1$ in the above corollary and get a~heap of size $\log N$ working in
1072 constant time per operation.