Stack Overflow
Stack Overflow

Questions tagged [fibonacci-heap]

A Fibonacci heap is an implementation of a priority queue that supports amortized O(1) insertion, merge, find-min, and decrease-key, along with amortized O(log n) delete and extract-min. When implemented with a Fibonacci heap, Dijkstra's algorithm and Prim's algorithm can be made to work in O(E + V log V).

77 questions
160
votes
5 answers

Has anyone actually implemented a Fibonacci-Heap efficiently?

Has anyone of you ever implemented a Fibonacci-Heap? I did so a few years back, but it was several orders of magnitude slower than using array-based BinHeaps. Back then, I thought of it as a valuable lesson in how research is not always as good as…
mdm
  • 5,528
  • 5
  • 29
  • 28
66
votes
1 answer

What is the intuition behind the Fibonacci heap data structure?

I've read the Wikipedia article on Fibonacci heaps and read CLRS's description of the data structure, but they provide little intuition for why this data structure works. Why are Fibonacci heaps designed the way they are? How do they work? Thanks!
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
39
votes
3 answers

Is there a standard Java implementation of a Fibonacci heap?

I was looking at the different kind of heap data structures. The Fibonacci heap seems to have the better worst case complexity for (1) insertion, (2) deletion and (2) finding the minimum element. I have found that in Java there is a class…
Phil
  • 3,375
  • 3
  • 30
  • 46
37
votes
4 answers

Real world applications of Binary heaps and Fibonacci Heaps

What are the real world applications of Fibonacci heaps and binary heaps? It'd be great if you could share some instance when you used it to solve a problem. Edit: Added binary heaps also. Curious to know.
softwarematter
  • 28,015
  • 64
  • 169
  • 263
29
votes
2 answers

Are Fibonacci heaps or Brodal queues used in practice anywhere?

Are Fibonacci heaps used in practice anywhere? I've looked around on SO and found answers to related questions (see below) but nothing that actually quite answers the question. There are good implementations of Fibonacci heaps out there, including…
kuzzooroo
  • 6,788
  • 11
  • 46
  • 84
21
votes
3 answers

How to implement Prim's algorithm with a Fibonacci heap?

I know Prim's algorithm and I know its implementation but always I skip a part that I want to ask now. It was written that Prim's algorithm implementation with Fibonacci heap is O(E + V log(V)) and my question is: what is a Fibonacci heap in…
user467871
19
votes
2 answers

Why is a Fibonacci heap called a Fibonacci heap?

The Fibonacci heap data structure has the word "Fibonacci" in its name, but nothing in the data structure seems to use Fibonacci numbers. According to the Wikipedia article: The name of Fibonacci heap comes from Fibonacci numbers which are used in…
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
13
votes
1 answer

Why do Fibonacci heaps need cascading cuts?

I'm learning f-heap from 'introduction to algorithms', and the 'decrease-key' operation really confuses me -- why does this need a 'cascading-cut' ? if this operation is removed: the cost of make-heap(), insert(), minimum() and union() remains…
exprosic
  • 630
  • 5
  • 17
11
votes
1 answer

Is there a Fibonacci heap based priority queue for Haskell?

Is there a Fibonacci heap/priority queue available for Haskell? (Or even an asymptotically better one?) I found a list of various priority queue implementations in this question, but I couldn't find if any of them satisfies the amortized running…
Petr
  • 62,528
  • 13
  • 153
  • 317
9
votes
4 answers

STL for Fibonacci Heap?

where is the Fibonacci Heap in STL ? and if STL do not implement Fibonacci Heap what is the best practice to implement it using existing algorithms and containers in STL ?
amin
  • 3,672
  • 5
  • 33
  • 61
8
votes
2 answers

Priority Queue - Skip List vs. Fibonacci Heap

I am interested in implementing a priority queue to enable an efficient Astar implementation that is also relatively simple (the priority queue is simple I mean). It seems that because a Skip List offers a simple O(1) extract-Min operation and an…
user_48349383
  • 517
  • 6
  • 13
5
votes
1 answer

Defining compare function for fibonacci heap in boost

I need to use Fibonacci heap in my project and I am trying to use it from boost library. But I cannot figure out how to set up a user defined compare function for arbitrary data type. I need to construct a min heap for struct node defined as…
cauthon14
  • 269
  • 1
  • 3
  • 14
5
votes
2 answers

Dijkstra on Java: Getting Interesting Results Using a Fibonacci Heap vs. PriorityQueue

I recently made an initial comparison of the running time of Dijkstra's algorithm using two data structures, the Java-based PriorityQueue (based on a binary heap, if I'm not mistaken), and a Fibonacci heap. I used Java's currentTimeMillis() to make…
Fiery Phoenix
  • 1,156
  • 2
  • 16
  • 30
5
votes
3 answers

What is the purpose behind marking some of the nodes in Fibonacci heap?

This picture from Wikipedia article has three nodes of a Fibonacci heap marked in blue . What is the purpose of some of the nodes being marked in this data structure ?
Geek
  • 26,489
  • 43
  • 149
  • 227
4
votes
2 answers

Find operation in Fibonacci Heap

I have this question when teaching myself Fibonacci Heap, which now I know is an efficient data structure to implement priority queue with amortized O(1) time complexity when decreasing priority of an element in the heap. However, from the CLRS…
Summer_More_More_Tea
  • 12,740
  • 12
  • 51
  • 83
1
2 3 4 5 6