Traditionally, computer scientists use a~variety of computational models
as a~formalism in which their algorithms are stated. If we were studying
-NP-completeness, we could safely assume that all the models are equivalent,
+NP-complete\-ness, we could safely assume that all the models are equivalent,
possibly up to polynomial slowdown which is negligible. In our case, the
differences between good and not-so-good algorithms are on a~much smaller
-scale. In this chapter, we will replace the usual ``yardsticks'' by a~micrometer,
+scale. In this chapter, we will replace the usual ``tape measure'' by a~micrometer,
state our computation models carefully and develop a repertoire of basic
data structures taking advantage of the fine details of the models.
On the other hand, we are interested in polynomial-time algorithms only, so $\Theta(\log N)$-bit
numbers should be sufficient. In practice, we pick~$W$ to be the larger of
$\Theta(\log N)$ and the size of integers used in the algorithm's input and output.
- We will call an integer which fits in a~single memory cell a~\df{machine word.}
+ We will call an integer that fits in a~single memory cell a~\df{machine word.}
\endlist
Both restrictions easily avoid the problems of unbounded parallelism. The first
standard complexity classes, but the calculations of time and space complexity tend
to be somewhat tedious. What more, when compared with the RAM with restricted
word size, the complexities are usually exactly $\Theta(W)$ times higher.
-This does not hold in general (consider a~program which uses many small numbers
+This does not hold in general (consider a~program that uses many small numbers
and $\O(1)$ large ones), but it is true for the algorithms we are interested in.
Therefore we will always assume that the operations have unit cost and we make
sure that all numbers are limited by the available word size.
\:Both restrictions at once.
\endlist
-Thorup discusses the usual techniques employed by RAM algorithms in~\cite{thorup:aczero}
+Thorup \cite{thorup:aczero} discusses the usual techniques employed by RAM algorithms
and he shows that they work on both Word-RAM and ${\rm AC}^0$-RAM, but the combination
of the two restrictions is too weak. On the other hand, the intersection of~${\rm AC}^0$
with the instruction set of modern processors is already strong enough (e.g., when we
algorithms, but the quadratic bound is good enough for our purposes.}
\qed
-\FIXME{Add references, especially to the unbounded parallelism remark.}
-
\thm
Every program for the PM running in polynomial time can be translated to a~program
computing the same on the Word-RAM with only $\O(1)$ slowdown.
techniques of design and analysis of randomized algorithms apply (see for
example Motwani and Raghavan~\cite{motwani:randalg}).
-\FIXME{Consult sources. Does it make more sense to generate random words at once on the RAM?}
-
\rem
There is one more interesting machine: the \df{Immutable Pointer Machine} (see
the description of LISP machines in \cite{benamram:pm}). It differs from the
%--------------------------------------------------------------------------------
-\section{Bucket sorting and contractions}\id{bucketsort}%
+\section{Bucket sorting and unification}\id{bucketsort}%
-The Contractive Bor\o{u}vka's algorithm (\ref{contbor}) needed to contract a~given
-set of edges in the current graph and flatten it afterwards, all this in time $\O(m)$.
-We have spared the technical details for this section and they will be useful
-in further algorithms, too.
+The Contractive Bor\o{u}vka's algorithm (\ref{contbor}) needs to contract a~given
+set of edges in the current graph and then flatten the graph, all this in time $\O(m)$.
+We have spared the technical details for this section, in which we are going to
+explain several rather general techniques based on bucket sorting.
-As already suggested, the contractions can be performed by building an~auxiliary
-graph and finding its connected components. Thus we will take care of the flattening
-only.
+As we have already suggested in the proof of Lemma \ref{contbor}, contractions
+can be performed in linear time by building an~auxiliary graph and finding its
+connected components. We will thus take care only of the subsequent flattening.
-\para
-On the RAM, it is sufficient to sort the edges lexicographically (each edge viewed
-as an~ordered pair of vertex identifiers with the smaller of the identifiers placed
-first). We can do that by a two-pass bucket sort with~$n$ buckets corresponding
-to the vertex identifiers.
+\paran{Flattening on RAM}%
+On the RAM, we can view the edges as ordered pairs of vertex identifiers with the
+smaller of the identifiers placed first and sort them lexicographically. This brings
+parallel edges together, so that a~simple linear scan suffices to find each bunch
+of parallel edges and remove all but the lightest one.
+Lexicographic sorting of pairs can be accomplished in linear time by a~two-pass
+bucket sort with $n$~buckets corresponding to the vertex identifiers.
However, there is a~catch in this. Suppose that we use the standard representation
of graphs by adjacency lists whose heads are stored in an array indexed by vertex
identifiers. When we contract and flatten the graph, the number of vertices decreases,
but if we inherit the original vertex identifiers, the arrays will still have the
-same size. Hence we spend a~super-linear amount of time on scanning the increasingly
+same size. We could then waste a~super-linear amount of time by scanning the increasingly
sparse arrays, most of the time skipping unused entries.
-To avoid this, we have to renumber the vertices after each contraction to component
-identifiers from the auxiliary graph and we create a~new vertex array. This way,
-the representation of the graph will be kept linear with respect to the size of the
-current graph.
+To avoid this problem, we have to renumber the vertices after each contraction to component
+identifiers from the auxiliary graph and create a~new vertex array. This helps
+keep the size of the representation of the graph linear with respect to its current
+size.
-\para
-The pointer representation of graphs does not suffer from sparsity as the vertices
+\paran{Flattening on PM}%
+The pointer representation of graphs does not suffer from sparsity since the vertices
are always identified by pointers to per-vertex structures. Each such structure
then contains all attributes associated with the vertex, including the head of its
adjacency list. However, we have to find a~way how to perform bucket sorting
-without arrays.
+without indexing of arrays.
+
+We will keep a~list of the per-vertex structures that defines the order of~vertices.
+Each such structure will be endowed with a~pointer to the head of the list of items in
+the corresponding bucket. Inserting an~edge to a~bucket can be then done in constant time
+and scanning the contents of all~$n$ buckets takes $\O(n+m)$ time.
+
+At last, we must not forget that while it was easy to \df{normalize} the pairs on the RAM
+by putting the smaller identifier first, this fails on the PM because we can directly
+compare the identifiers only for equality. We can work around this again by bucket-sorting:
+we sort the multiset $\{ (x,i) \mid \hbox{$x$~occurs in the $i$-th pair} \}$ on~$x$.
+Then we reset all pairs and re-insert the values back in their increasing order.
+This is also $\O(n+m)$.
+
+\paran{Tree isomorphism}%
+Another nice example of pointer-based radix sorting is a~Pointer Machine algorithm for
+deciding whether two rooted trees are isomorphic. Let us assume for a~moment that
+the outdegree of each vertex is at most a~fixed constant~$k$. We begin by sorting the subtrees
+of both trees by their depth. This can be accomplished by running depth-first search to calculate
+the depths and bucket-sorting them with $n$~buckets afterwards.
+
+Then we proceed from depth~0 to the maximum depth and for each of them we identify
+the isomorphism equivalence classes of subtrees of that particular depth. We will assign
+unique identifiers all such classes; at most~$n+1$ of them are needed as there are
+$n+1$~subtrees in the tree (including the empty subtree). As the PM does not
+have numbers as a~first-class type, we create a~``\df{yardstick}'' ---a~list
+of $n+1$~distinct items--- and we use pointers to these ``ticks'' as identifiers.
+When we are done, isomorphism of the whole trees can be decided by comparing the
+identifiers assigned to their roots.
+
+Suppose that classes of depths $0,\ldots,d-1$ are already computed and we want
+to identify those of depth~$d$. We will denote their count of~$n_d$. We take
+a~root of every such tree and label it with an~ordered $k$-tuple of identifiers
+of its subtrees; when it has less than $k$ sons, we pad the tuple with empty
+subtrees. Tuples corresponding to isomorphic subtrees are identical up to
+reordering of elements. We therefore sort the codes inside each tuple and then
+sort the tuples, which brings the equivalent tuples together.
+
+The first sort (inside the tuples) would be easy on the RAM, but on the PM we
+have to use the normalization trick mentioned above. The second sort is
+a~straightforward $k$-pass bucket sort.
+
+If we are not careful, a~single sorting pass takes $\O(n_d + n)$ time, because
+while we have only $n_d$~items to sort, we have to scan all $n$~buckets. This can
+be easily avoided if we realize that the order of buckets does not need to be
+fixed --- in every pass, we can use a~completely different order and it still
+does bring the equivalent tuples together. Thus we can keep a~list of buckets
+which are used in the current pass and look only inside these buckets. This way,
+we reduce the time spent in a~single pass to $\O(n_d)$ and the whole algorithm
+takes $\O(\sum_d n_d) = \O(n)$.
+
+Our algorithm can be easily modified for trees with unrestricted degrees.
+We replace the fixed $d$-tuples by general sequences of identifiers. The first
+sort does not need any changes. In the second sort, we proceed from the first
+position to the last one and after each bucket-sorting pass we put aside the sequences
+that have just ended. They are obviously not equivalent to any other sequences.
+The second sort is linear in the sum of the lengths of the sequences, which is
+$n_{d+1}$ for depth~$d$. We can therefore decide isomorphism of the whole trees
+in time $\O(\sum_d (n_d + n_{d+1})) = \O(n)$.
+
+The unification of sequences by bucket sorting will be useful in many
+other situations, so we will state it as a~separate lemma:
+
+\lemman{Sequence unification}\id{suniflemma}%
+Partitioning of a~collection of sequences $S_1,\ldots,S_n$, whose elements are
+arbitrary pointers and symbols from a~finite alphabet, to equality classes can
+be performed on the Pointer Machine in time $\O(n + \sum_i \vert S_i \vert)$.
+
+\rem
+The first linear-time algorithm that partitions all subtrees to isomorphism equivalence
+classes is probably due to Zemlayachenko \cite{zemlay:treeiso}, but it lacks many
+details. Dinitz et al.~\cite{dinitz:treeiso} have recast this algorithm in modern
+terminology and filled the gaps. Our algorithm is easier to formulate than those,
+because it replaces the need for auxiliary data structures by more elaborate bucket
+sorting.
+
+\paran{Topological graph computations}%
+Many graph algorithms are based on the idea of so called \df{micro/macro decomposition:}
+We decompose a~graph to subgraphs on roughly~$k$ vertices and solve the problem
+separately inside these ``micrographs'' and in the ``macrograph'' obtained by
+contraction of the micrographs. If $k$~is small enough, many of the micrographs
+are isomorphic, so we can compute the result only once for each isomorphism class
+and recycle it for all micrographs in that class. On the other hand, the macrograph
+is roughly $k$~times smaller than the original graph, so we can use a~less efficient
+algorithm and it will still run in linear time with respect to the size of the original
+graph.
+
+This kind of decomposition is traditionally used for trees, especially in the
+algorithms for the Lowest Common Ancestor problem (cf.~Section \ref{verifysect}
+and the survey paper \cite{alstrup:nca}) and for online maintenance of marked ancestors
+(cf.~Alstrup et al.~\cite{alstrup:marked}). Let us take a~glimpse at what happens when
+we decompose a~tree with $k$ set to~$1/4\cdot\log n$. There are at most $2^{2k} = \sqrt n$ non-isomorphic subtrees of size~$k$,
+because each isomorphism class is uniquely determined by the sequence of $2k$~up/down steps
+performed by depth-first search. Suppose that we are able to decompose the input and identify
+the equivalence classes of microtrees in linear time, then solve the problem in time $\O(\poly(k))$ for
+each microtree and finally in $\O(n'\log n')$ for the macrotree of size $n'=n/k$. When we put these pieces
+together, we get an~algorithm for the whole problem which achieves time complexity $\O(n
++ \sqrt{n}\cdot\poly(\log n) + n/\log n\cdot\log(n/\log n)) = \O(n)$.
+
+Decompositions are usually implemented on the RAM, because subgraphs can be easily
+encoded in numbers, which can be then used to index arrays containing the precomputed
+results. As the previous algorithm for subtree isomorphism shows, indexing is not strictly
+required for identifying equivalent microtrees and it can be replaced by bucket
+sorting on the Pointer Machine. Buchsbaum et al.~\cite{buchsbaum:verify} have extended
+this technique to general graphs in form of so called topological graph computations.
+Let us define them.
+
+\defn
+A~\df{graph computation} is a~function that takes a~\df{labeled undirected graph} as its input. The labels of its
+vertices and edges can be arbitrary symbols drawn from a~finite alphabet. The output
+of the computation is another labeling of the same graph. This time, the vertices and
+edges can be labeled with not only symbols of the alphabet, but also with pointers to the vertices
+and edges of the input graph, and possibly also with pointers to outside objects.
+A~graph computation is called \df{topological} if it produces isomorphic
+outputs for isomorphic inputs. The isomorphism of course has to preserve not only
+the structure of the graph, but also the labels in the obvious way.
+
+\obs
+The topological graph computations cover a~great variety of graph problems, ranging
+from searching for matchings or Eulerian tours to finding Hamilton circuits.
+The MST problem itself however does not belong to this class, because we do not have any means
+of representing the edge weights as labels, unless of course there is only a~fixed amount
+of possible values.
+
+As in the case of tree decompositions, we would like to identify the equivalent subgraphs
+and process only a~single instance from each equivalence class. The obstacle is that
+graph isomorphism is known to be computationally hard (it is one of the few
+problems that are neither known to lie in~$\rm P$ nor to be $\rm NP$-complete;
+see Arvind and Kurur \cite{arvind:isomorph} for recent results on its complexity).
+We will therefore manage with a~weaker form of equivalence, based on some sort
+of graph encodings:
+
+\defn
+A~\df{canonical encoding} of a~given labeled graph represented by adjacency lists
+is obtained by running the depth-first search on the graph and recording its traces.
+We start with an~empty encoding. When we enter
+a~vertex, we assign an~identifier to it (again using a~yardstick to represent numbers)
+and we append the label of this vertex to the encoding. Then we scan all back edges
+going from this vertex and append the identifiers of their destinations, accompanied
+by the edges' labels. Finally we append a~special terminator to mark the boundary
+between the code of this vertex and its successor.
+
+\obs
+The canonical encoding is well defined in the sense that non-iso\-morphic graphs always
+receive different encodings. Obviously, encodings of isomorphic graphs can differ,
+depending on the order of vertices and also of the adjacency lists. A~graph
+on~$n$ vertices with $m$~edges is assigned an~encoding of length at most $2n+2m$ ---
+for each vertex, we record its label and a~single terminator; edges contribute
+by identifiers and labels. These encodings can be constructed in linear time and
+in the same time we can also create a~graph corresponding to any encoding.
+We will use the encodings for our unification of graphs:
+
+\defn
+For a~collection~$\C$ of graphs, we define $\vert\C\vert$ as the number of graphs in
+the collection and $\Vert\C\Vert$ as their total size, i.e., $\Vert\C\Vert = \sum_{G\in\C} n(G) + m(G)$.
-We will keep a~list of the per-vertex structures which defines the order of~vertices.
-Each such structure will contain a~pointer to the head of the corresponding bucket,
-again stored as a~list. Putting an~edge to a~bucket can be done in constant time then,
-scanning all~$n$ buckets takes $\O(n+m)$ time.
+\lemman{Graph unification}\id{guniflemma}%
+A~collection~$\C$ of labeled graphs can be partitioned into classes which share the same
+canonical encoding in time $\O(\Vert\C\Vert)$ on the Pointer Machine.
-\FIXME{Add an example of locally determined orders, e.g., tree isomorphism?}
+\proof
+Construct canonical encodings of all the graphs and then apply the Sequence unification lemma
+(\ref{suniflemma}) on them.
+\qed
+
+\para
+When we want to perform a~topological computation on a~collection~$\C$ of graphs
+with $k$~vertices, we first precompute its result for a~collection~$\cal G$ of \df{generic graphs}
+corresponding to all possible canonical encodings on $k$~vertices. Then we use unification to match
+the \df{actual graphs} in~$\C$ to the generic graphs in~$\cal G$. This gives us the following
+theorem:
+
+\thmn{Topological computations, Buchsbaum et al.~\cite{buchsbaum:verify}}\id{topothm}%
+Suppose that we have a~topological graph computation~$\cal T$ that can be performed in time
+$T(k)$ for graphs on $k$~vertices. Then we can run~$\cal T$ on a~collection~$\C$
+of labeled graphs on~$k$ vertices in time $\O(\Vert\C\Vert + (k+s)^{k(k+2)}\cdot (T(k)+k^2))$,
+where~$s$ is a~constant depending only on the number of symbols used as vertex/edge labels.
+
+\proof
+A~graph on~$k$ vertices has less than~$k^2/2$ edges, so the canonical encodings of
+all such graphs are shorter than $2k + 2k^2/2 = k(k+2)$. Each element of the encoding
+is either a~vertex identifier, or a~symbol, or a~separator, so it can attain at most $k+s$
+possible values for some fixed~$s$.
+We can therefore enumerate all possible encodings and convert them to a~collection $\cal G$
+of all generic graphs such that $\vert{\cal G}\vert \le (k+s)^{k(k+2)}$ and $\Vert{\cal G}\Vert
+\le \vert{\cal G}\vert \cdot k^2$.
+
+We run the computation on all generic graphs in time $\O(\vert{\cal G}\vert \cdot T(k))$
+and then we use the Unification lemma (\ref{guniflemma}) on the union of the collections
+$\C$ and~$\cal G$ to match the generic graphs with the equivalent actual graphs in~$\C$
+in time $\O(\Vert\C\Vert + \Vert{\cal G}\Vert)$.
+Finally we create a~copy of the generic result for each of the actual graphs.
+If the computation uses pointers to the input vertices in its output, we have to
+redirect them to the actual input vertices, which we can do by associating
+the output vertices that refer to an~input vertex with the corresponding places
+in the encoding of the input graph. This way, the whole output can be generated in time
+$\O(\Vert\C\Vert + \Vert{\cal G}\Vert)$.
+\qed
+
+\rem
+The topological computations and the Graph unification lemma will play important
+roles in Sections \ref{verifysect} and \ref{optalgsect}.
%--------------------------------------------------------------------------------
\section{Data structures on the RAM}
\id{ramdssect}
-There is a~lot of data structures designed specifically for the RAM, taking
-advantage of both indexing and arithmetics. In many cases, they surpass the known
-lower bounds for the same problem on the~PM and they often achieve constant time
+There is a~lot of data structures designed specifically for the RAM. These structures
+take advantage of both indexing and arithmetics and they often surpass the known
+lower bounds for the same problem on the~PM. In many cases, they achieve constant time
per operation, at least when either the magnitude of the values or the size of
the data structure are suitably bounded.
-A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt},
-which represent a~subset of the integers $\{0,\ldots,U-1\}$, allowing insertion,
+A~classical result of this type are the trees of van Emde Boas~\cite{boas:vebt}
+which represent a~subset of the integers $\{0,\ldots,U-1\}$. They allow insertion,
deletion and order operations (minimum, maximum, successor etc.) in time $\O(\log\log U)$,
regardless of the size of the subset. If we replace the heap used in the Jarn\'\i{}k's
algorithm (\ref{jarnik}) by this structure, we immediately get an~algorithm
for finding the MST in integer-weighted graphs in time $\O(m\log\log w_{max})$,
-where $w_{max}$ is the maximum weight. We will show later that it is even
-possible to achieve linear time complexity for arbitrary integer weights.
+where $w_{max}$ is the maximum weight.
-A~real breakthrough has been made by Fredman and Willard, who introduced
-the Fusion trees~\cite{fw:fusion} which again perform membership and predecessor
-operation on a~set of $n$~integers, but this time with complexity $\O(\log_W n)$
+A~real breakthrough has been however made by Fredman and Willard who introduced
+the Fusion trees~\cite{fw:fusion}. They again perform membership and predecessor
+operation on a~set of $n$~integers, but with time complexity $\O(\log_W n)$
per operation on a~Word-RAM with $W$-bit words. This of course assumes that
each element of the set fits in a~single word. As $W$ must at least~$\log n$,
-the operations take $\O(\log n/\log\log n)$ and we are able to sort $n$~integers
+the operations take $\O(\log n/\log\log n)$ time and thus we are able to sort $n$~integers
in time~$o(n\log n)$. This was a~beginning of a~long sequence of faster and
faster sorting algorithms, culminating with the work by Thorup and Han.
They have improved the time complexity of integer sorting to $\O(n\log\log n)$ deterministically~\cite{han:detsort}
and expected $\O(n\sqrt{\log\log n})$ for randomized algorithms~\cite{hanthor:randsort},
both in linear space.
-Despite the recent progress, the corner-stone of most RAM data structures
-is still the representation of data structures by integers introduced by Fredman
-and Willard. It will also form a~basis for the rest of this chapter.
-
-\FIXME{Add more history.}
+The Fusion trees themselves have very limited use in graph algorithms, but the
+principles behind them are ubiquitous in many other data structures and these
+will serve us well and often. We are going to build the theory of Q-heaps in
+Section \ref{qheaps}, which will later lead to a~linear-time MST algorithm
+for arbitrary integer weights in Section \ref{iteralg}. Other such structures
+will help us in building linear-time RAM algorithms for computing the ranks
+of various combinatorial structures in Chapter~\ref{rankchap}.
+
+Outside our area, important consequences of these data structures include the
+Thorup's $\O(m)$ algorithm for single-source shortest paths in undirected
+graphs with positive integer weights \cite{thorup:usssp} and his $\O(m\log\log
+n)$ algorithm for the same problem in directed graphs \cite{thorup:sssp}. Both
+algorithms have been then significantly simplified by Hagerup
+\cite{hagerup:sssp}.
+
+Despite the progress in the recent years, the corner-stone of all RAM structures
+is still the representation of combinatorial objects by integers introduced by
+Fredman and Willard. It will also form a~basis for the rest of this chapter.
%--------------------------------------------------------------------------------
$x_0,\ldots,x_{d-1}$.
\para
-If we want to fit the whole vector in a~single word, the parameters $b$ and~$d$ must satisty
+If we want to fit the whole vector in a~single word, the parameters $b$ and~$d$ must satisfy
the condition $(b+1)d\le W$.
By using multiple-precision arithmetics, we can encode all vectors satisfying $bd=\O(W)$.
We will now describe how to translate simple vector manipulations to sequences of $\O(1)$ RAM operations
i.e., the smallest~$i$ such that $\alpha[i]=1$.
By a~combination of subtraction with $\bxor$, we create a~number
-which contains ones exactly at the position of $\<LSB>(\alpha)$ and below:
+that contains ones exactly at the position of $\<LSB>(\alpha)$ and below:
\alik{
\alpha&= \9\9\9\9\9\1\0\0\0\0\cr
\endalgo
\rem
-We have used a~plenty of constants which depend on the format of the vectors.
+We have used a~plenty of constants that depend on the format of the vectors.
Either we can write non-uniform programs (see \ref{nonuniform}) and use native constants,
or we can observe that all such constants can be easily manufactured. For example,
$(\0^b\1)^d = \1^{(b+1)d} / \1^{b+1} = (2^{(b+1)d}-1)/(2^{b+1}-1)$. The only exceptions
in an~encompassing algorithm, so we usually can spend a~lot of time on the precalculation
of constants performed once during algorithm startup.
+\rem
+The history of combining arithmetic and logical operations to obtain fast programs for various
+interesting functions is blurred. Many of the ``bit tricks'' we have described have been
+discovered independently by numerous people in the early ages of digital computers.
+Since then, they have become a~part of the computer science folklore. Probably the
+earliest documented occurrence is in the 1972's memo of the MIT Artificial Intelligence
+Lab \cite{hakmem}. However, until the work of Fredman and Willard nobody seemed to
+realize the full consequences.
+
%--------------------------------------------------------------------------------
\section{Q-Heaps}\id{qheaps}%
This guarantees that $k\le W^{1/4}$ and $\O(2^{k^4}) = \O(N)$. Let us however
remark that the whole construction is primarily of theoretical importance
and that the huge constants involved everywhere make these heaps useless
-in practical algorithms. Many of the tricks used however prove themselves
-useful even in real-life implementations.
+in practical algorithms. Despise this, many of the tricks we develop have proven
+themselves useful even in real-life implementations.
Spending the time on reprocessing makes it possible to precompute tables for
almost arbitrary functions and then assume that they can be evaluated in
to observe that $2^{\O(k^3)}\cdot \poly(k) = \O(2^{k^4})$.
\qed
-\para
+\paran{Tries and ranks}%
We will first show an~auxiliary construction based on tries and then derive
the real definition of the Q-heap from it.
A~\df{compressed trie} is obtained from the trie by removing the vertices of outdegree~1
except for the root and marked vertices.
-Whereever is a~directed path whose internal vertices have outdegree~1 and they carry
-no mark, we replace this path by a~single edge labeled with the contatenation
-of the original edge's labels.
+Wherever is a~directed path whose internal vertices have outdegree~1 and they carry
+no mark, we replace this path by a~single edge labeled with the concatenation
+of the original edges' labels.
In both kinds of tries, we order the outgoing edges of every vertex by their labels
lexicographically.
\defn
For our set~$X$, we define~$T$ as a~compressed trie for the set of binary
-encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W ; x\in X \}$.
+encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W \mid x\in X \}$.
\obs
The trie~$T$ has several interesting properties. Since all words in~$S$ have the same
where~$\(x)$ disagrees with a~label. Before this point, all edges not taken by
the search were leading either to subtrees containing elements all smaller than~$x$
or all larger than~$x$ and the only values not known yet are those in the subtree
-below the edge which we currently consider. Now if $x[b]=0$ (and therefore $x<x_i$),
+below the edge that we currently consider. Now if $x[b]=0$ (and therefore $x<x_i$),
all values in that subtree have $x_j[b]=1$ and thus they are larger than~$x$. In the other
case, $x[b]=1$ and $x_j[b]=0$, so they are smaller.
\qed
-\para
+\paran{A~better representation}%
The preceding lemma shows that the rank can be computed in polynomial time, but
unfortunately the variables on which it depends are too large for a~table to
be efficiently precomputed. We will carefully choose an~equivalent representation
of the trie which is compact enough.
\lemma\id{citree}%
-The trie is uniquely determined by the order of the guides~$g_1,\ldots,g_{n-1}$.
+The compressed trie is uniquely determined by the order of the guides~$g_1,\ldots,g_{n-1}$.
\proof
We already know that the letter depths of the trie vertices are exactly
for a~newly inserted element in constant time. However, the set is too large
to fit in a~vector and we cannot perform insertion on an~ordinary array in
constant time. This can be worked around by keeping the set in an~unsorted
-array together with a~vector containing the permutation which sorts the array.
+array together with a~vector containing the permutation that sorts the array.
We can then insert a~new element at an~arbitrary place in the array and just
update the permutation to reflect the correct order.
(a~vector of $\O(n\log k)$ bits; we will write $x_i$ for $X[\varrho(i)]$),
\:$B$ --- a~set of ``interesting'' bit positions
(a~sorted vector of~$\O(n\log W)$ bits),
-\:$G$ --- the function which maps the guides to the bit positions in~$B$
+\:$G$ --- the function that maps the guides to the bit positions in~$B$
(a~vector of~$\O(n\log k)$ bits),
\:precomputed tables of various functions.
\endlist
\algout The $i$-th smallest element in the heap.
\endalgo
-\para
+\paran{Extraction}%
The heap algorithms we have just described have been built from primitives
operating in constant time, with one notable exception: the extraction
$x[B]$ of all bits of~$x$ at positions specified by the set~$B$. This cannot be done
time using the results of section \ref{bitsect} and Lemma \ref{qhxtract}.
\qed
-\rem
+\paran{Combining Q-heaps}%
We can also use the Q-heaps as building blocks of more complex structures
like Atomic heaps and AF-heaps (see once again \cite{fw:transdich}). We will
show a~simpler, but useful construction, sometimes called the \df{Q-heap tree.}
projects / saga.git / blobdiff