Re: High-performance Priority Queue / Heap for glib

[Ben Pfaff <blp cs stanford edu>]

Maik Zumstrull <maik zumstrull rz uni-karlsruhe de> writes:

[about a Fibonacci heap implementation]
> | - Does it offer significant (big-o) performance 
> |   benefits for a common operation, or allow some 
> |   operation that would be really hard to code without 
> |   the data structure?
>
> All operations can be done with existing glib data structures, but
> there is a significant performance benefit. Please refer to
> <http://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times>.
>
> Glib includes linked lists and balanced trees, of course; a simple heap
> was submitted in 2003. As you can see, all three structures are easily
> beaten by this approach, dropping performance to O(1) for most
> operations and retaining O(log n) performance in the other cases.

The big-O of a Fibonacci heap is better than that of a balanced
tree or a binary heap, but how is the actual performance?  When
you benchmark your Fibonacci heap against balanced trees or
binary heaps for realistic test cases, is there an actual
improvement in runtime?

The reason that I ask is this paragraph in the chapter on
Fibonacci heaps in Cormen, Leiserson, and Rivest, _Introduction
to Algorithms_:

        From a practical point of view, however, the constant
        factors and programming complexity of Fibonacci heaps
        make them less desirable than ordinary binary (or k-ary)
        heaps for most applications.  Thus, Fibonacci heaps are
        predominantly of theoretical interest.

I observed this effect in practice myself a few years ago, when I
compared the performance of otherwise identical code using a
binary heap and a Fibonacci heap (see page 51 of
http://benpfaff.org/uniformity/uniformity-2001.04.27.pdf).  But I
didn't make much of an attempt to optimize my heaps, and maybe
you did a better implementation.
-- 
Ben Pfaff 
http://benpfaff.org