+\obs\id{qhsetb}%
+The set~$B$ has $\O(k\log W)=\O(W)$ bits, so it can be stored in a~constant number
+of machine words in form of a~sorted vector. The function~$G$ can be also stored as a~vector
+of $\O(k\log k)$ bits. We can change a~single~$g_i$ in constant time using
+vector operations: First we delete the original value of~$g_i$ from~$B$ if it
+is not used anywhere else. Then we add the new value to~$B$ if it was not
+there yet and we write its position in~$B$ to~$G(i)$. Whenever we insert
+or delete a~value in~$B$, the values at the higher positions shift one position
+up or down and we have to update the pointers in~$G$. This can be fortunately
+accomplished by adding or subtracting a~result of vector comparison.
+
+In this representation, we can reformulate our lemma on ranks as follows:
+
+\lemma\id{qhrank}%
+The rank $R_X(x)$ can be computed in constant time from:
+\itemize\ibull
+\:the function~$G$,
+\:the values $x_1,\ldots,x_n$,
+\:the bit string~$x[B]$,
+\:$x$ itself.
+\endlist
+
+\proof
+Let us prove that all ingredients of Lemma~\ref{qhdeterm} are either small
+enough or computable in constant time.
+
+We know that the shape of the trie~$T$ is uniquely determined by the order of the $g_i$'s
+and therefore by the function~$G$ since the array~$B$ is sorted. The shape of
+the trie together with the bits in $x[B]$ determine the leaf~$x_i$ found when searching
+for~$x$ using only the guides. This can be computed in polynomial time and it
+depends on $\O(k\log k)$ bits of input, so according to Lemma~\ref{qhprecomp}
+we can look it up in a~precomputed table.
+
+The relation between $x$ and~$x_i$ can be obtained directly as we know the~$x_i$.
+The bit position of the first disagreement can be calculated in constant time
+using the LSB/MSB algorithm (\ref{lsb}).
+
+All these ingredients can be stored in $\O(k\log k)$ bits, so we may assume
+that the rank can be looked up in constant time as well.
+\qed
+
+\para
+In the Q-heap we would like to store the set~$X$ as a~sorted array together
+with the corresponding trie, which will allow us to determine the position
+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.
+We can then insert a~new element at an~arbitrary place in the array and just
+update the permutation to reflect the correct order.
+
+We are now ready for the real definition of the Q-heap and for the description
+of the basic operations on it.
+
+\defn
+A~\df{Q-heap} consists of:
+\itemize\ibull
+\:$k$, $n$ --- the capacity of the heap and the current number of elements (word-sized integers),
+\:$X$ --- the set of word-sized elements stored in the heap (an~array of words in an~arbitrary order),
+\:$\varrho$ --- a~permutation on~$\{1,\ldots,n\}$ such that $X[\varrho(1)] < \ldots < X[\varrho(n)]$
+(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$
+(a~vector of~$\O(n\log k)$ bits),
+\:precomputed tables of various functions.
+\endlist
+
+\algn{Search in the Q-heap}\id{qhfirst}%
+\algo
+\algin A~Q-heap and an~integer~$x$ to search for.
+\:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
+\:If $i\le n$ return $x_i$, otherwise return {\sc undefined.}
+\algout The smallest element of the heap which is greater or equal to~$x$.
+\endalgo
+
+\algn{Insertion to the Q-heap}
+\algo
+\algin A~Q-heap and an~integer~$x$ to insert.
+\:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
+\:If $x=x_i$, return immediately (the value is already present).
+\:Insert the new value to~$X$:
+\::$n\=n+1$.
+\::$X[n]\=x$.
+\::Insert~$n$ at the $i$-th position in the permutation~$\varrho$.
+\:Update the $g_j$'s:
+\::Move all~$g_j$ for $j\ge i$ one position up. \hfil\break
+ This translates to insertion in the vector representing~$G$.
+\::Recalculate $g_{i-1}$ and~$g_i$ according to the definition.
+ \hfil\break Update~$B$ and~$G$ as described in~\ref{qhsetb}.
+\algout The updated Q-heap.
+\endalgo
+
+\algn{Deletion from the Q-heap}
+\algo
+\algin A~Q-heap and an~integer~$x$ to be deleted from it.
+\:$i\=R_X(x)+1$, using Lemma~\ref{qhrank} to calculate the rank.
+\:If $i>n$ or $x_i\ne x$, return immediately (the value is not in the heap).
+\:Delete the value from~$X$:
+\::$X[\varrho(i)]\=X[n]$.
+\::Find $j$ such that~$\varrho(j)=n$ and set $\varrho(j)\=\varrho(i)$.
+\::$n\=n-1$.
+\:Update the $g_j$'s like in the previous algorithm.
+\algout The updated Q-heap.
+\endalgo
+
+\algn{Finding the $i$-th smallest element in the Q-heap}\id{qhlast}%
+\algo
+\algin A~Q-heap and an~index~$i$.
+\:If $i<1$ or $i>n$, return {\sc undefined.}
+\:Return~$x_i$.
+\algout The $i$-th smallest element in the heap.
+\endalgo
+
+\para
+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
+in~$\O(1)$ time on the Word-RAM, but we can implement it with ${\rm AC}^0$
+instructions as suggested by Andersson in \cite{andersson:fusion} or even
+with those ${\rm AC}^0$ instructions present on real processors (see Thorup
+\cite{thorup:aczero}). On the Word-RAM, we need to make use of the fact
+that the set~$B$ is not changing too much --- there are $\O(1)$ changes
+per Q-heap operation. As Fredman and Willard have shown, it is possible
+to maintain a~``decoder'', whose state is stored in $\O(1)$ machine words,
+and which helps us to extract $x[B]$ in a~constant number of operations:
+
+\lemman{Extraction of bits}\id{qhxtract}%
+Under the assumptions on~$k$, $W$ and the preprocessing time as in the Q-heaps,\foot{%
+Actually, this is the only place where we need~$k$ to be as low as $W^{1/4}$.
+In the ${\rm AC}^0$ implementation, it is enough to ensure $k\log k\le W$.
+On the other hand, we need not care about the exponent because it can
+be arbitrarily increased using the Q-heap trees described below.}
+it is possible to maintain a~data structure for a~set~$B$ of bit positions,
+which allows~$x[B]$ to be extracted in $\O(1)$ time for an~arbitrary~$x$.
+When a~single element is inserted to~$B$ or deleted from~$B$, the structure
+can be updated in constant time, as long as $\vert B\vert \le k$.
+
+\proof
+See Fredman and Willard \cite{fw:transdich}.
+\qed
+
+\para
+This was the last missing bit of the mechanics of the Q-heaps. We are
+therefore ready to conclude this section by the following theorem
+and its consequences:
+
+\thmn{Q-heaps, Fredman and Willard \cite{fw:transdich}}\id{qh}%
+Let $W$ and~$k$ be positive integers such that $k=\O(W^{1/4})$. Let~$Q$
+be a~Q-heap of at most $k$-elements of $W$~bits each. Then the Q-heap
+operations \ref{qhfirst} to \ref{qhlast} on~$Q$ (insertion, deletion,
+search for a~given value and search for the $i$-th smallest element)
+run in constant time on a~Word-RAM with word size~$W$, after spending
+time $\O(2^{k^4})$ on the same RAM on precomputing of tables.
+
+\proof
+Every operation on the Q-heap can be performed in a~constant number of
+vector operations and calculations of ranks. The ranks are computed
+in $\O(1)$ steps involving again $\O(1)$ vector operations, binary
+logarithms and bit extraction. All these can be calculated in constant
+time using the results of section \ref{bitsect} and Lemma \ref{qhxtract}.
+\qed
+
+\rem
+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.}
+Suppose we have a~Q-heap of capacity~$k$ and a~parameter $d\in{\bb N}^+$. We
+can build a~balanced $k$-ary tree of depth~$d$ such that its leaves contain
+a~given set and every internal vertex keeps the minimum value in the subtree
+rooted in it, together with a~Q-heap containing the values in all its sons.
+This allows minimum to be extracted in constant time (it is placed in the root)
+and when any element is changed, it is sufficient to recalculate the values
+from the path from this element to the root, which takes $\O(d)$ Q-heap
+operations.
+
+\corn{Q-heap trees}\id{qhtree}%
+For every positive integer~$r$ and $\delta>0$ there exists a~data structure
+capable of maintaining the minimum of a~set of at most~$r$ word-sized numbers
+under insertions and deletions. Each operation takes $\O(1)$ time on a~Word-RAM
+with word size $W=\Omega(r^{\delta})$, after spending time
+$\O(2^{r^\delta})$ on precomputing of tables.
+
+\proof
+Choose $\delta' \le \delta$ such that $r^{\delta'} = \O(W^{1/4})$. Build
+a~Q-heap tree of depth $d=\lceil \delta/\delta'\rceil$ containing Q-heaps of
+size $k=r^{\delta'}$. \qed
+
+\rem\id{qhtreerem}%
+When we have an~algorithm with input of size~$N$, the word size is at least~$\log N$
+and we can spend time $\O(N)$ on preprocessing, so we can choose $r=\log N$ and
+$\delta=1$ in the above corollary and get a~heap of size $\log N$ working in
+constant time per operation.
projects / saga.git / blobdiff