From Keith Schwarz:

Hi Dan-

I'm sorry for the delay in getting back to you! I hadn't actually thought of a license for the Fibonacci Heap, but I think it should be fine to release your port under the Apache v2 license.

Hope this helps!

-Keith