The algorithm and its data structures.

We have described efficient methods for computing the co-occurrences and for partially sorting the mutual information values. What we aim to create is a mechanism that will output the edges $(u,v)$ in decreasing order of their mutual information. We shall set up this mechanism in the form of a Fibonacci heap [Fredman, Tarjan 1987] called $vheap$ that contains an element for each $u\in V$, represented by the edge with the highest mutual information among the edges $(u,v)$, with $v\prec u$, that are not yet eliminated. The record in $vheap$ is of the form $(N_{uv},u,v,I_{uv})$, with $v\prec u$, and with $I_{uv}$ being the key used for sorting. Once the maximum is extracted, the used edge has to be replaced by the next largest (in terms of $I_{uv}$) edge in $u$'s lists. To perform this latter task we use the data structures shown in Figure 20. Kruskal's algorithm is now used to construct the desired spanning tree. Figure 21 summarizes the resulting algorithm.

Figure 21: The ACCL algorithm.