Fibonacci heaps are very interesting beasts, but implementation is slightly complicated. For C++ developers there's one in Boost that is not so easy to use quickly.

I've recently put an alternative one in C++11 here: https://github.com/beniz/fiboheap