In the course of the development of my main research project, Scotch, I needed to sort elements according to several criteria, which might not always be single integer values. Consequently, the bucket sorting algorithms that I used before were not adequate. After looking at the Red-Black tree data structure (a thoughtful description and implementation of which can be found here), I turned to the Fibonacci heap (also called «Fibonacci trees», since it is technically a forest of trees with given degree properties), which better fitted my needs. Indeed, in the context of graph partitioning, I planned to use this data structure to select the best vertex to move from one part to another, depending on the improvement such a move may bring to the current partition. Such local optimisation algorithms are classically referred to as «Fiduccia-Mattheyses» or «Kernighan-Lin», depending on the way vertices are moved or swapped between parts. In such algorithms, once a vertex of best gain value has been selected for moving, the gains of all its neighbors have to be recomputed. Consequently, the data structure will be subject to much more deletion and insertion operations of «unsorted» arbitrary elements than to searches for, and deletions of, elements of best gain value. By adding and removing arbitrary vertices quickly (in constant time for addition), and by postponing the expensive sorting operations up to the moment when searching for the element of extremal value, Fibonacci trees are just what I needed when list buckets cannot be used.
However, all of the existing free/libre implementations that I could find on the Internet had two drawbacks. First, all of them were recursive, incurring a heavy recursion cost for a few useful instructions per function call. Second, all of them treated elements as independent data structures, which were internally allocated and freed at insertion and deletion time. Both of these features made them completely inappropriate for the kind of heavy use that I had in mind, for which such routines have to be called millions of times, and vertex elements are already embodied within data structures such as hash table arrays (yes, high performance computing can be real fun in terms of data structures!).
Consequently, I wrote my own, de-recursived, implementation of the Fibonacci trees data structure. The code is small, as this is really a very elegant data structure. Save for the pointer array internally used by the consolidation routine, no memory allocation is performed by this module. The allocation and freeing of the individual elements is left to the users of the module, who can opt for the kind of memory handling that they want. Unlike most implementations, the element of minimum value is not internally recorded, as I had no need to preserve it; however, module users can easily implement this feature on top of the existing routines. All module routines, except the consolidation routine which computes the current extremal value, are written as macros, which can be used as is or embodied within regular functions, depending on the pre-definition of symbolic constants.
Fibonacci trees are handled by means of a
structure. Elements to be inserted and searched for must comprise
FiboNode substructure. Elements can belong to several
tree structures, provided they possess as many
substructures as needed, and provided that users have a means for
determining the offset of the element structure from the pointer to
FiboNode which is returned by the module routines.
The module routines are the following:
FiboTreedata structure, by allocating the internal consolidation array.
FiboTreedata structure, by freeing the internal consolidation array. Tree elements are not modified in any way. If elements have to be individually processed at freeing time, for instance to be freed themselves, then they have to be removed one by one from the tree before
fiboTreeExitis called, or be handled by means of external iterators (for instance by traversing their support array if they were all allocated together).
FiboTreedata structure become free, by removing all of its elements. Like for
fiboTreeExit, tree elements are not themselves considered nor modified in any way. Their chaining pointers just become meaningless, so that removing any previously inserted
FiboNodeelement from a freed tree may lead to segmentation violation errors.
FiboTree. At the time being, this routine just calls
fiboTreeConsolidate. Module users willing to keep track of the element of extremal gain can redefine this routine, as well as the
fiboTreeDelroutines, such that a pointer to the element of extremal gain is preserved in the
FiboTreedata structure. The recorded element must be compared against elements which are removed and deleted, and updated whenever necessary (which may require a call to
fiboTreeConsolidateif the extremal element is the one which is being removed from the
FIBO_DEBUGdebugging flag has been set at compile time, this routine checks the consistency of the given
The tarball of my implementation of the Fibonacci tree module can be obtained here. It contains files fibo.c, fibo.h, and test_fibo.c, as a sample use. I have placed this version of my module under a CeCILL-B license (equivalent in its principle to a «BSD» license), for maximal re-use.