Boost Fibonacci Heap Decrease Operation

Question

The new 'heap' boost library includes a fibonacci heap. The complexity of each implementation can be seen here: http://www.boost.org/doc/libs/1_51_0/doc/html/heap/data_structures.html.

My question is this: Why is the fibonacci heap decrease operation O(log(N)), while the increase operation is O(1)?

I would like to experiment with using the fibonacci heap in Dijkstra's algorithm, which is heavily dependent upon a fast decrease operation.

Answer 1

According to http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html

boost.heap implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast to the typical textbook design, which uses min-heaps.

The textbook/wikipedia Fibonacci heap has the highest priority element with the lowest value, aka a min-heap (e.g. "1" is higher priority than "2"). STL and Boost (for consistency with STL) reverse the definition so that the highest priority has the highest value, aka a max-heap (i.e. a "2" higher priority than "1").

Essentially it means that decrease and increase have inverse meanings between textbook and Boost.

If you want to get a min-heap (like the textbook definitions), you must first defined an appropriate boost::heap::compare functor for your fibonacci_heap (see an example here: Defining compare function for fibonacci heap in boost), then call increase whenever you decrease the value associated with a heap element (and are thus increasing the priority) and vice-versa.