opt.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Approaching Optimality}
   6
   7 \section{Soft heaps}
   8
   9 Recently, Chazelle \cite{chazelle:ackermann} and Pettie \cite{pettie:ackermann}
  10 have presented algorithms for the MST with worst-case time complexity
  11 $\O(m\timesalpha(m,n))$. We will devote this chapter to their results
  12 and especially to another algorithm by Pettie and Ramachandran \cite{pettie:optimal},
  13 which is provably optimal.
  14
  15 At the very heart of all these algorithms lies the \df{soft heap} discovered by
  16 Chazelle \cite{chazelle:softheap}. It is a~meldable priority queue, roughly
  17 similar to the Vuillemin's binomial heaps \cite{vuillemin:binheap} or Fredman's
  18 and Tarjan's Fibonacci heaps \cite{ft:fibonacci}. The soft heaps run faster at
  19 the expense of \df{corrupting} a~fraction of the inserted elements by raising
  20 their values (the values are however never decreased). This allows for
  21 an~trade-off between accuracy and speed controlled by a~parameter~$\varepsilon$.
  22 The heap operations take $\O(\log(1/\varepsilon))$ amortized time and at every
  23 moment at most~$\varepsilon n$ elements of the~$n$ elements inserted can be
  24 corrupted.
  25
  26 \defnn{Soft heap operations}%
  27 The soft heap contains distinct elements from a~totally ordered universe and it
  28 supports the following operations:
  29 \itemize\ibull
  30 \:$\<Create>(\varepsilon)$ --- create an~empty soft heap with the given accuracy parameter,
  31 \:$\<Insert>(H,x)$ --- insert a~new element~$x$ to the heap~$H$,
  32 \:$\<Meld>(H_1,H_2)$ --- form a~new soft heap containing the elements stored in two disjoint
  33   heaps $H_1$ and~$H_2$
  34   (both heaps must have the same~$\varepsilon$ and they are destroyed in the process),
  35 \:$\<DeleteMin>(H)$ --- delete the minimum element of the heap~$H$ and return its value
  36   (optionally signalling that the value has been corrupted).
  37 \endlist
  38
  39 \figure{softheap1.eps}{\epsfxsize}{XXXX}
  40
  41 \figure{softheap2.eps}{\epsfxsize}{XXXX}
  42
  43 \defnn{Soft queues}
  44 The soft heap is built from \df{soft queues} (we will omit the adjective soft
  45 in the rest of this section). Each queue has a~shape of a~binary tree.\foot{%
  46 Actually, Chazelle defines the queues as binomial trees, but he transforms them in ways that are
  47 somewhat counter-intuitive, albeit well-defined. We prefer describing the queues as binary
  48 trees with a~special distribution of values. In fact, we get this exact type of binary
  49 trees from the natural correspondence between general rooted trees and binary trees
  50 (as described for example in Knuth's Fundamental Algorithms \cite{knuth:fundalg}).
  51 Also, the original C~code in the Chazelle's paper uses this representation internally.}
  52 Each vertex~$v$ of the tree remembers a~linked list $\<list>(v)$ of values. The first value in the list
  53 is called the \df{controlling key} of the vertex, denoted by $\<ckey>(v)$ and defined to be~$+\infty$ if the
  54 list is empty. The item list in every left son will be used only temporarily and it
  55 will be kept empty between operations. Only right sons and the root have their lists
  56 permanently occupied. (See the picture.)
  57
  58 Each vertex is also assigned its \df{rank,} which is a~non-negative integer $\<rank>(v)$.
  59 The rank of leaves is always zero, the rank of every internal vertex must be strictly
  60 greater than the ranks of its sons.
  61
  62 \obs
  63 The rank of the root.....
  64 Complete binary trees.....
  65 The master tree.....
  66
  67
  68 \endpart