[saga.git] / opt.tex

\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Approaching Optimality}

\section{Soft heaps}

Recently, Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann}
have presented algorithms for the MST with worst-case time complexity
$\O(m\timesalpha(m,n))$. We will devote this chapter to their results
and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal},
which is provably optimal.

At the very heart of all these algorithms lies the \df{soft heap} discovered by
Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly
similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
the expense of \df{corrupting} a~fraction of the inserted elements by raising
their values (the values are however never decreased). This allows for
an~trade-off between accuracy and speed controlled by a~parameter~$\varepsilon$.
The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every
moment at most~$\varepsilon n$ elements of the~$n$ elements inserted can be
corrupted.

\defnn{Soft heap operations}%
The soft heap contains distinct elements from a~totally ordered universe and it
supports the following operations:
\itemize\ibull
\:$\<Create>(\varepsilon)$ --- create an~empty soft heap with the given accuracy parameter,
\:$\<Insert>(H,x)$ --- insert a~new element~$x$ to the heap~$H$,
\:$\<Meld>(P,Q)$ --- merge two heaps into one, more precisely insert all elements of a~heap~$Q$
  to the heap~$P$, destroying~$Q$ in the process (both heaps must have the same~$\varepsilon$),
\:$\<DeleteMin>(H)$ --- delete the minimum element of the heap~$H$ and return its value
  (optionally signalling that the value has been corrupted).
\endlist

\defnn{Soft queues}
The soft heap is built from \df{soft queues} (we will omit the adjective soft
in the rest of this section). Each queue has a~shape of a~binary tree.\foot{%
Actually, Chazelle defines the queues as binomial trees, but he transforms them in ways that are
somewhat counter-intuitive, albeit well-defined. We prefer describing the queues as binary
trees with a~special distribution of values. In fact, the original C~code in the Chazelle's
paper uses this representation internally.}
Each vertex~$v$ of the tree remembers a~doubly-linked list $\<list>(v)$ of values. The
item list in every left son will be used only temporarily and it will be kept
empty between operations. Only right sons and the root have their lists
permanently occupied. The former vertices will be called \df{white}, the latter
\df{black.} (See the picture.)

The first value in the list is called the \df{controlling key} of the vertex,
denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used
value or we set $\<ckey>(v)=+\infty$. The \<ckey>'s obey the standard \df{heap order}
--- a~\<ckey> of a~parent is always less than the \<ckey>'s of its sons.

Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
The rank of leaves is always zero, the rank of every internal vertex must be strictly
greater than the ranks of its sons. We define the rank of a~queue to be equal to the
rank of its root vertex and similarly for its \<ckey>.

A~queue is called \df{complete} if every two vertices joined by an~edge have rank
difference exactly one. In other words, it is a~complete binary tree and the
ranks correspond to vertex heights.

\figure{softheap1.eps}{\epsfxsize}{\multicap{A~complete and a~partial soft queue tree\\
(black vertices contain items, numbers indicate ranks)}}

\obs
A~complete queue of rank~$k$ contains exactly~$2^{k+1}-1$ vertices, $2^k$~of which are
black (by induction). Any other queue can be trivially embedded to a~complete queue of the same
rank, which we will call the \df{master tree} of the queue. This embedding preserves vertex
ranks, colors and the ancestor relation.

The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
of the original roots and also its \<ckey>. To preserve the heap order, we will choose
the one whose \<ckey> is smaller.

Sometimes, we will need to split a~queue to smaller queues. We will call this operation
\df{dismantling} the queue and it will happen only in cases when the item list in the root
is empty. It suffices to remove the leftmost (all white) path going from the root. From
a~queue of rank~$k$, we get queues of ranks $0,1,\ldots,k-1$, some of which may be missing
if the original queue was not complete.

We will now combine the soft queues to the soft heap.

\figure{softheap2.eps}{\epsfxsize}{Joining and dismantling of soft queues}

\defn A~\df{soft heap} consists of:
\itemize\ibull
\:a~doubly linked list of soft queues of distinct ranks (in increasing order of ranks),
  we will call the first queue the \df{head}, the last queue will be its \df{tail};
\:\df{suffix minima:} each queue contains a~pointer to the queue with minimum \<ckey>
of those following it in the list;
\:and a~global parameter~$r\in{\bb N}$, to be set depending on~$\varepsilon$.
\endlist
\>The heap always keeps the \df{Rank invariant:} When a~root of a~tree has rank~$k$,
its leftmost path has length at least~$k/2$.

\para
\em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble
the heap with the smaller maximum rank and we insert its queues to the other heap.
If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
a~single queue of rank~$k+1$ as already described and we propagate the new queue as
a~\df{carry} to the next iteration, similarly to addition of binary numbers.
Finally we have to update the suffix minima by walking the new list backwards
from the last inserted item.

\em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating
a~single-element heap and melding it to the destination heap.

\algn{Creating a~new soft heap}
\algo
\algin A~parameter~$\varepsilon$.
\:Allocate memory for a~new heap structure~$H$.
\:Initialize the list of queues in~$H$ as an~empty list.
\:Set the parameter~$r$ to~$2\lceil\log(1/\varepsilon)\rceil+2$ (to be justified later).
\algout A~newly minted soft heap~$H$.
\endalgo

\algn{Melding of two soft heaps}
\algo
\algin Two soft heaps~$P$ and~$Q$.
\:If the tail of~$P$ has smaller rank than the tail of~$Q$, exchange their item lists.
\brk\cmt{Whenever we run into an~end of a~list, we assume that it contains an~empty queue of infinite rank.}
\:$p\=\<head>(P)$.
\:While $Q$ still has some queues:
\::$q\=\<head>(Q)$.
\::If $\<rank>(p) < \<rank>(q)$, then $p\=$ the successor of~$p$,
\::else if $\<rank>(p) > \<rank>(q)$, remove~$q$ from~$Q$ and insert it before~$p$,
\::otherwise (the ranks are equal, we need to propagate the carry):
\:::$\<carry>=p$.
\:::$p\=$ the successor of~$p$.
\:::While $\<rank>(q)=\<rank>(\<carry>)$:
\::::Remove~$q$ from~$Q$.
\::::$\<carry>\=\<join>(q, \<carry>)$.
\::::$q\=\<head>(Q)$.
\:::Insert~\<carry> before~$q$.
\:Update the suffix minima: Walk with~$p$ backwards to the head of~$P$:
\::$p'\=$ successor of~$p$.
\::If $\<ckey>(p) < \<ckey>(p')$, set $\<suffix\_min>(p)\=p$.
\::Otherwise set $\<suffix\_min>(p)\=\<suffix\_min>(p')$.
\:Destroy the heap~$Q$.
\algout The merged heap~$P$.
\endalgo

\algn{Insertion of an~element to a~soft heap}
\algo
\algin A~heap~$H$ and a~new element~$x$.
\:Create a~new heap~$H'$ with the same parameters as~$H$. Let~$H'$ contain a~sole queue of rank~0,
  whose only vertex has the element~$x$ in its item list.
\:$\<Meld>(H,H')$.
\algout An~updated heap~$H$.
\endalgo

\para
So far, the mechanics of the soft heaps was almost identical to the binomial heaps
and the reader could rightfully yawn. The things are going to get interesting
now as we approach the parts where corruption of items takes place.

If all item lists contain at most one item equal to the \<ckey> of the particular
vertex, no information is lost and the heap order guarantees that the minimum item
of every queue stays in its root. We can however allow longer lists and let the items
stored in a~single list travel together between the vertices of the tree, still
represented by a~common \<ckey>. This data-structural analogue of car pooling will
allow the items to travel at a~faster rate, but as only a~single item can be equal
to the \<ckey>, all other items will be inevitably corrupted.

We of course have to be careful about the size of the lists, as we must avoid corrupting
too many items. We will control the growth according to the vertex ranks. Vertices
with rank at most~$r$ will always contain just a~single item. Above this level,
the higher is the rank, the longer list will we allow.

\para
\em{Deleting of minimum} will follow this principle. The minimum is easy to locate
--- we follow the \<suffix\_min> of the head of the heap to the queue with the minimum
\<ckey> and we look inside the item list of the root of this queue. We remove the \em{last}
item from the list (we do not want the \<ckey> to change) and return it as the minimum.
(It is not necessarily the real minimum of all items, but always the minimum of those
uncorrupted.)

If the list becomes empty, we \em{refill} it with items from the lower levels of the
same tree. This can be best described recursively: We ask the left son to refill itself
(remember that the left son is always white, so there are no items to lose). If the new
\<ckey> of the left son is smaller than of the right son, we immediately move the left
son's list to its parent. Otherwise, we exchange the sons and move the list from the
new left son to the parent. This way, we obey the heap order and the same time we keep
the white left son free of items.

Ocassionally, we repeat this process once again and we concatenate the resulting lists
(we append the latter list to the former, using the smaller of the two \<ckey>'s). This
makes the lists grow longer and we want to do that roughly on every other level of the
tree. The exact condition will be that either the rank of the current vertex is odd,
or the difference in ranks between this vertex and its right son is at least two.

If refilling of the left son fails because there are no more items in that subtree
(we report this by setting its \<ckey> to $+\infty$), the current vertex is no longer
needed, as the items would just travel through it unmodified. We therefore want to
remove it. Instead of deleting it directly, we will rather make it point to its former
grandsons and we will remove the (now orhpaned) original son. This helps us to ensure
that both sons always have the same rank, which will be useful for the analysis.

When all refilling is done, we update the suffix minima by walking from the current
queue to the head of the heap exactly as we did in the \<Meld> procedure.

Our only remaining worry is that the Rank invariant can be broken after the
refilling. When the leftmost path of the tree becomes too short, we just
\em{dismantle} the tree as already described and we meld the new trees back to
the heap. This is easier to handle when the item list at the root vertex is
empty. We will therefore move this check before the refilling of the root list.
It will turn out that we have enough time to always walk the leftmost path
completely, so no explicit counters are needed.

Let us translate these ideas to real (pseudo)code:

\algn{Deleting the minimum item of a~soft heap}
\algo
\algin A~soft heap~$H$.
\:Use \<suffix\_min> of the head queue of~$H$ to locate the queue~$q$ with the smallest \<ckey>.
\:Remove the last element~$x$ of the item list in the root of~$q$.
\:If the item list is empty:
\::Count the vertices on the leftmost path of~$q$.
\::If there are less than $\<rank>(q)$ of them:
\:::Remove~$q$ from the list of queues.
\:::Recalculate the suffix minima as in the \<Meld> procedure.
\:::Dismantle~$q$ and create a~heap~$H'$ holding the resulting trees.
\:::Meld them back: $\<Meld>(H,H')$.
\::Otherwise:
\:::Call \<Refill> on the root of~$q$.
\:::If $\<ckey>(q)=+\infty$ (no items left), remove the tree~$q$.
\:::Recalculate the suffix minima.
\algout The deleted minimum item~$x$ (possibly corrupted).
\endalgo

\algn{Refilling the item list of a~vertex}
\algo
\algin A~soft queue and its vertex~$v$ with an~empty item list.
\:Handle trivial cases: If~$v$ has no children or both have $\<ckey>=+\infty$,
  set $\<ckey>(v)$ to~$+\infty$ and return.
\:Let \<left> and~\<right> denote the sons of~$v$.
\:Recurse: call $\<Refill>(\<left>)$.
\:If $\<ckey>(\<left>) > \<ckey>(\<right>)$, swap the sons.
\:Move the item list from \<left> to~$v$ (implying $\<ckey>(v)=\<ckey>(\<left>)$).
\:If $\<rank>(v)$ is odd or $\<rank>(v) > \<rank>(\<right>)+1$, recurse once more:
\::Repeat steps 3--4.
\::Append the item list from \<left> to the item list at~$v$.
\:Clean up. If $\<ckey>(\<right>) = +\infty$:
\::If $\<ckey>(\<left>) = +\infty$: unlink and discard both sons.
\::Otherwise relink the sons of \<left> to~$v$ and discard \<left>.
\algout A~modified soft queue.
\endalgo



\endpart