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 \defnn{Soft queues}
  40 The soft heap is built from \df{soft queues} (we will omit the adjective soft
  41 in the rest of this section). Each queue has a~shape of a~binary tree.\foot{%
  42 Actually, Chazelle defines the queues as binomial trees, but he transforms them in ways that are
  43 somewhat counter-intuitive, albeit well-defined. We prefer describing the queues as binary
  44 trees with a~special distribution of values. In fact, the original C~code in the Chazelle's
  45 paper uses this representation internally.}
  46 Each vertex~$v$ of the tree remembers a~linked list $\<list>(v)$ of values. The
  47 item list in every left son will be used only temporarily and it will be kept
  48 empty between operations. Only right sons and the root have their lists
  49 permanently occupied. The former vertices will be called \df{white}, the latter
  50 \df{black.} (See the picture.)
  51
  52 The first value in the list is called the \df{controlling key} of the vertex,
  53 denoted by $\<ckey>(v)$. If the list is empty, we keep the most recently used
  54 value or we set $\<ckey>(v)=+\infty$. The \<ckey>'s obey the standard \df{heap order}
  55 --- a~\<ckey> of a~parent is always less than the \<ckey>'s of its sons.
  56
  57 Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
  58 The rank of leaves is always zero, the rank of every internal vertex must be strictly
  59 greater than the ranks of its sons. We define the rank of a~queue to be equal to the
  60 rank of its root vertex and similarly for its \<ckey>.
  61
  62 A~queue is called \df{complete} if every two vertices joined by an~edge have rank
  63 difference exactly one. In other words, it is a~complete binary tree and the
  64 ranks correspond to vertex heights.
  65
  66 \figure{softheap1.eps}{\epsfxsize}{\multicap{A~complete and a~partial soft queue tree\\
  67 (black vertices contain items, numbers indicate ranks)}}
  68
  69 \obs
  70 A~complete queue of rank~$k$ contains exactly~$2^{k+1}-1$ vertices, $2^k$~of which are
  71 black (by induction). Any other queue can be trivially embedded to a~complete queue of the same
  72 rank, which we will call the \df{master tree} of the queue. This embedding preserves vertex
  73 ranks, colors and the ancestor relation.
  74
  75 The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining}
  76 two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one
  77 of the original roots and also its \<ckey>. To preserve the heap order, we will choose
  78 the one whose \<ckey> is smaller.
  79
  80 Sometimes, we will need to split a~queue to smaller queues. We will call this operation
  81 \df{dismantling} the queue and it will happen only in cases when the item list in the root
  82 is empty. It suffices to remove the leftmost (all white) path going from the root. From
  83 a~queue of rank~$k$, we get queues of ranks $0,1,\ldots,k-1$, some of which may be missing
  84 if the original queue was not complete.
  85
  86 We will now combine the soft queues to the soft heap.
  87
  88 \figure{softheap2.eps}{\epsfxsize}{Joining and dismantling soft queues}
  89
  90 \defn A~\df{soft heap} consists of:
  91 \itemize\ibull
  92 \:a~doubly linked list of soft queues of distinct ranks (in increasing order of ranks),
  93   we will call the first queue the \df{head}, the last queue will be its \df{tail};
  94 \:\df{suffix minima:} each queue contains a~pointer to the queue with minimum \<ckey>
  95 of those following it in the list;
  96 \:and a~global parameter~$r\in{\bb N}$, to be set depending on~$\varepsilon$.
  97 \endlist
  98 \>The heap always keeps the \df{Rank invariant:} When a~root of a~tree has rank~$k$,
  99 its leftmost path has length at least~$k/2$.
 100
 101 \para
 102 \em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble
 103 the heap with the smaller maximum rank and we insert its queues to the other heap.
 104 If two queues of the same rank~$k$ appear in both lists, we \em{join} them to
 105 a~single queue of rank~$k+1$ as already described and we propagate the new queue as
 106 a~\df{carry} to the next iteration, similarly to addition of binary numbers.
 107 Finally we have to update the suffix minima by walking the new list backwards
 108 from the last inserted item.
 109
 110 \em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating
 111 a~single-element heap and melding it to the destination heap.
 112
 113 \algn{Creating a~new soft heap}
 114 \algo
 115 \algin A~parameter~$\varepsilon$.
 116 \:Allocate memory for a~new heap structure~$H$.
 117 \:Initialize the list of queues in~$H$ as an~empty list.
 118 \:Set the parameter~$r$ to~$2\lceil\log(1/\varepsilon)\rceil+2$ (to be justified later).
 119 \algout A~newly minted soft heap~$H$.
 120 \endalgo
 121
 122 \algn{Melding of two soft heaps}
 123 \algo
 124 \algin Two soft heaps~$H_1$ and~$H_2$.
 125 \:If the tail of~$H_1$ has smaller rank than the tail of~$H_2$, exchange $H_1$ and~$H_2$.
 126 \brk\cmt{Whenever we run into an~end of a~list, we assume that it contains an~empty queue of infinite rank.}
 127 \:$p\=\<head>(H_1)$.
 128 \:While $H_2$ still has some queues:
 129 \::$q\=\<head>(H_2)$.
 130 \::If $\<rank>(p) < \<rank>(q)$, then $p\=$ the successor of~$p$,
 131 \::else if $\<rank>(p) > \<rank>(q)$, remove~$q$ from~$H_2$ and insert it before~$p$,
 132 \::otherwise (the ranks are equal, we need to propagate the carry):
 133 \:::$\<carry>=p$.
 134 \:::$p\=$ the successor of~$p$.
 135 \:::While $\<rank>(q)=\<rank>(\<carry>)$:
 136 \::::Remove~$q$ from~$H_2$.
 137 \::::$\<carry>\=\<join>(q, \<carry>)$.
 138 \::::$q\=\<head>(H_2)$.
 139 \:::Insert~\<carry> before~$q$.
 140 \:Update the suffix minima: Walk with~$p$ backwards to the head of~$H_1$:
 141 \::$p'\=$ successor of~$p$.
 142 \::If $\<ckey>(p) < \<ckey>(p')$, set $\<suffix\_min>(p)\=p$.
 143 \::Otherwise set $\<suffix\_min>(p)\=\<suffix\_min>(p')$.
 144 \:Destroy the heap~$H_2$.
 145 \algout The merged heap~$H_1$.
 146 \endalgo
 147
 148 \algn{Insertion of an~element to a~soft heap}
 149 \algo
 150 \algin A~heap~$H$ and a~new element~$x$.
 151 \:Create a~new heap~$H'$ containing a~sole queue of rank~0, whose only vertex has
 152   the element~$x$ in its item list.
 153 \:$\<Meld>(H,H')$.
 154 \algout An~updated heap~$H$.
 155 \endalgo
 156
 157
 158 \endpart