From 2281f2c9b2f8e979a77ce2255cb29408b2499519 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 1 Mar 2008 13:42:56 +0100 Subject: [PATCH] More on Q-heaps. --- ram.tex | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 82 insertions(+), 9 deletions(-) diff --git a/ram.tex b/ram.tex index f327f38..df7aa41 100644 --- a/ram.tex +++ b/ram.tex @@ -638,21 +638,21 @@ of constants performed once during algorithm startup. \section{Q-Heaps}\id{qheaps}% -We have shown how to perform relatively complicated operations on a~set of values +We have shown how to perform non-trivial operations on a~set of values in constant time, but so far only under the assumption that the number of these values is small enough and that the values themselves are also small enough (so that the whole set fits in $\O(1)$ machine words). Now we will show how to lift the restriction on the magnitude of the values and still keep constant time -complexity. We will describe a~simplified version of the Q-Heaps developed by +complexity. We will describe a~simplified version of the Q-heaps developed by Fredman and Willard in~\cite{fw:transdich}. -The Q-Heap represents a~set of at most~$k$ word-sized integers, where $k\le W^{1/4}$ +The Q-heap represents a~set of at most~$k$ word-sized integers, where $k\le W^{1/4}$ and $W$ is the word size of the machine. It will support insertion, deletion, finding -of minimum, and other operations described below, in constant time, provided that +of minimum and maximum, and other operations described below, in constant time, provided that we are willing to spend~$\O(2^{k^4})$ time on preprocessing. The exponential-time preprocessing may sound alarming, but a~typical application uses -Q-Heaps of size $k=\log^{1/4} N$, where $N$ is the size of the algorithm's input, +Q-heaps of size $k=\log^{1/4} N$, where $N$ is the size of the algorithm's input, which 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 @@ -675,7 +675,7 @@ to observe that $2^{\O(k^3)}\cdot \O(k^c) = \O(2^{k^4})$. \para We will first show an~auxiliary construction based on tries and then derive -the actual definition of the Q-Heap from it. +the actual definition of the Q-heap from it. \nota Let us introduce some notation first: @@ -747,7 +747,7 @@ return the correct leave, for all~$x$ outside~$X$ it will no longer fail and instead it will land in some leaf $x_i$. We will call the index of this leaf $T(x)$. At the first sight this vertex may seem unrelated, but we will show that it can be used to determine the rank of~$x$ in~$X$, which will later form a~basis -for all other Q-Heap operations: +for all other Q-heap operations: \lemma\id{qhdeterm}% The rank $R_X(x)$ is uniquely determined by a~combination of: @@ -810,7 +810,7 @@ The set~$B$ has $\O(k\log W)=\O(W)$ bits, so it can be stored in a~constant numb of machine words as a~vector. The function~$C$ can be also stored as a~vector of $k\log k$ bits. -\lemma +\lemma\id{qhrank}% The rank $R_X(x)$ can be computed in constant time from: \itemize\ibull \:the function~$C$, @@ -829,12 +829,85 @@ we can look it up in a~precomputed table. Similarly we will determine all other ingredients of Lemma~\ref{qhdeterm} in constant time. As we know~$x$ and all the $x_i$'s, we can immediately find -the relation $x$ and $x_{T[x]}$ and use the LSB/MSB algorithm (\ref{lsb}) +the relation between $x$ and $x_{T[x]}$ and use the LSB/MSB algorithm (\ref{lsb}) to find the topmost disagreeing bit. 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 a~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 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), +\:$C$ --- the function determining the order of bits as tested by the trie +(a~vector of~$\O(n\log k)$ bits), +\:precomputed tables of various functions. +\endlist + +\algn{Search in the Q-heap} +\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$ and insert~$r$ at the $i$-th position in the permutation~$\varrho$. +\:Update the $c_i$'s: + Insert a~new element between~$C(i-1)$ and~$C(i)$ and recalculate $c_{i-1}$ and + the new~$c_i$ according to the definition. For each changed~$c_j$: +\::If the new value of~$c_j$ is not in~$B$, insert it there. +\::\FIXME{Update~$C$ on shifts in~$B$} +\::Update $C(j)$ to point at the position of~$c_j$ in~$B$. +\::If the old value of the~$c_j$ is no longer used, delete it from~$B$. +\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 $c_i$'s like in the previous algorithm. +\algout The updated Q-heap. +\endalgo + +\algn{Finding the $i$-th smallest element in the Q-heap} +\algo +\algin A~Q-heap and an~index~$i$. +\:If $i<1$ or $i>n$, return {\sc undefined.} +\:Return $X[\varrho(i)]$. +\algout The $i$-th smallest element in the heap. +\endalgo \endpart -- 2.39.2