\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>(H_1,H_2)$ --- form a~new soft heap containing the elements stored in two disjoint
  heaps $H_1$ and~$H_2$
  (both heaps must have the same~$\varepsilon$ and they are destroyed in the process),
\:$\<DeleteMin>(H)$ --- delete the minimum element of the heap~$H$ and return its value
  (optionally signalling that the value has been corrupted).
\endlist

\figure{softheap1.eps}{\epsfxsize}{XXXX}

\figure{softheap2.eps}{\epsfxsize}{XXXX}

\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, we get this exact type of binary
trees from the natural correspondence between general rooted trees and binary trees
(as described for example in Knuth's Fundamental Algorithms \cite{knuth:fundalg}).
Also, the original C~code in the Chazelle's paper uses this representation internally.}
Each vertex~$v$ of the tree remembers a~linked list $\<list>(v)$ of values. The first value in the list
is called the \df{controlling key} of the vertex, denoted by $\<ckey>(v)$ and defined to be~$+\infty$ if the
list is empty. 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. (See the picture.)

Each vertex is also assigned its \df{rank,} which is a~non-negative integer $\<rank>(v)$.
The rank of leaves is always zero, the rank of every internal vertex must be strictly
greater than the ranks of its sons.

\obs
The rank of the root.....
Complete binary trees.....
The master tree.....


\endpart
