their values (the values are however never lowered). This allows for
a~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
+moment at most~$\varepsilon n$ elements of the $n$~elements inserted can be
corrupted.
\defnn{Soft heap interface}%
Each vertex is also assigned its \df{rank,} which is a~non-negative integer.
The ranks of leaves are always zero, the rank of every internal vertex can be
-arbitrary, but it must be strictly greater than the ranks of its sons. We
-define the rank of the whole queue to be equal to the rank of its root vertex and
-similarly for its \<ckey>.
+arbitrary, but it must be strictly greater than the ranks of its sons. Also,
+we will always maintain the ranks in such a~way that both sons will have the
+equal ranks. We define the rank of the whole 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
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 at the same time we keep
the white left son free of items.
+\looseness=1 %%HACK%%
Occasionally, 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
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:
+%%HACK%%
+\>Let us translate these ideas to real (pseudo)code:
\algn{Deleting the minimum item from a~soft heap}
\algo
Before we estimate the time spent on deletions, we analyse the refills.
\lemma
-Every invocation of the \<Refill> procedure takes time $\O(1)$ amortized.
+Every invocation of \<Refill> takes time $\O(1)$ amortized.
\proof
When \<Refill> is called from the \<DeleteMin> operation, it recurses on a~subtree of the
that have created them.
\qed
-It remains to take care of the calculation with ranks:
+%%HACK%%
+\>It remains to take care of the calculation with ranks:
\lemma\id{shyards}%
Every manipulation with ranks performed by the soft heap operations can be
and the sum of these differences telescopes, again to the real cost of the meld.
\qed
-Now we can put the bits together and laurel our effort with the following theorem:
+We can put the bits together now and laurel our effort with the following theorem:
\thmn{Performance of soft heaps, Chazelle \cite{chazelle:softheap}}\id{softheap}%
A~soft heap with error rate~$\varepsilon$ ($0<\varepsilon\le 1/2$) processes
When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are done.
Otherwise we observe that the edges $e,f$ adjacent to~$c$ on this cycle cannot be corrupted
(they would be in~$R^C$ otherwise, which is impossible). By contractibility of~$C$ there exists
-a~path~$P$ in~$C\crpt (R\cap C)$ such that all edges of~$P$ are lighter than $e$ or~$f$ and hence
+a~path~$P$ in~$C\crpt (R\cap C)$ such that all edges of~$P$ are lighter than $e$~or~$f$ and hence
also than~$g$. The weights of the edges of~$P$ in the original graph~$G$ cannot be higher than
in~$G\crpt R$, so the path~$P$ is lighter than~$g$ even in~$G$ and we can again perform the
trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst(G)$.
\qed
\para
-We still intend to mimic the Iterative Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
+We still intend to mimic the Iterated Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$
of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that got corrupted in the process.
We recursively compute the MSF of those subgraphs and of the contracted graph. Then we take the
union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce
the MSF of~$G$, but a~sparser graph containing it, on which we can continue.
-We can formulate the exact partitioning algorithm and its properties as follows:
+%%HACK%%
+\>We can formulate the exact partitioning algorithm and its properties as follows:
\algn{Partition a~graph to a~collection of contractible clusters}\id{partition}%
\algo
so the number of candidate decision trees is bounded by
$(n^4+2^{n^2})^{2^{2n^2+1}} \le 2^{(n^2+1)\cdot 2^{2n^2+1}} \le 2^{2^{2n^2+2}} \le 2^{2^{3n^2}}$.
-We will enumerate the trees in an~arbitrary order, test each of them for correctness and
+We enumerate the trees in an~arbitrary order, test each tree for correctness and
find the shallowest tree among those correct. Testing can be accomplished by running
through all possible permutations of edges, each time calculating the MSF using any
of the known algorithms and comparing it with the result given by the decision tree.
The number of permutations does not exceed $(n^2)! \le (n^2)^{n^2} \le n^{2n^2} \le 2^{n^3}$
-and each permutation can be checked in time $\O(\poly(n))$.
+for sufficiently large~$n$ and each one can be checked in time $\O(\poly(n))$.
On the Pointer Machine, trees and permutations can be certainly enumerated in time
$\O(\poly(n))$ per object. The time complexity of the whole algorithm is therefore
upper bound on the optimal algorithm:
\thmn{Upper bound on complexity of the Optimal algorithm}\id{optthm}%
-The time complexity of the Optimal MST algorithm is $\O(m\alpha(m,n))$.
+The time complexity of the Optimal MST algorithm is $\O(m\timesalpha(m,n))$.
\proof
We bound $D(m,n)$ by the number of comparisons performed by the algorithm of Chazelle \cite{chazelle:ackermann}