5 \chapter{Approaching Optimality}
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.
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
26 \defnn{Soft heap operations}%
27 The soft heap contains distinct elements from a~totally ordered universe and it
28 supports the following operations:
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
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).
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, we get this exact type of binary
45 trees from the natural correspondence between general rooted trees and binary trees
46 (as described for example in Knuth's Fundamental Algorithms \cite{knuth:fundalg}).
47 Also, the original C~code in the Chazelle's paper uses this representation internally.}
48 Each vertex~$v$ of the tree remembers a~linked list $\<list>(v)$ of values. The first value in the list
49 is called the \df{controlling key} of the vertex, denoted by $\<ckey>(v)$ and defined to be~$+\infty$ if the
50 list is empty. The item list in every left son will be used only temporarily and it
51 will be kept empty between operations. Only right sons and the root have their lists
52 permanently occupied. (See the picture.)
54 Each vertex is also assigned its \df{rank,} which is a~non-negative integer $\<rank>(v)$.
55 The rank of leaves is always zero, the rank of every internal vertex must be strictly
56 greater than the ranks of its sons.
59 The rank of the root.....
60 Complete binary trees.....