Real world applications of Binary heaps and Fibonacci Heaps [closed]

Question

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.

Bentonbentonite

"Real world use" seems to be asking the wrong question, similar to "what are real world uses of arrays?" – Workable

Everyone knows the real world use of arrays! – Bentonbentonite

Contrast how many time have to used Fibonacci heaps to the number of times you have used arrays in your entire programming life. – Bentonbentonite

Related: Has anyone actually implemented a Fibonacci heap efficiently?. Executive summary: Binary heaps outperform Fibonacci in most real-world applications, unless the underlying graph is very dense. This is basically because a binary heap can be efficiently implemented using an array, but a Fibonacci heap is implemented as a system of pointers. – Handedness

As it stands, this question is way too general for SO. It may have been on-topic 7 years ago, but it isn't on-topic now. Blame @H.Pauwelyn for bumping it to the front page. – Celom

@devnull: it is way to broad by today's site standards. I've re-closed it to reflect that. – Johiah

Fibonacci heaps are an incredibly specific kind of heap that was invented to prove a bound. The "practical" data structure you would use among the pointer-based heaps would be the pairing heap, which are particularly useful in workloads where you do a lot of heap merges. If you don't need merge or decrease-key, then usually you just want whichever heap is in the standard library, which is usually a binary or 4-ary heap implemented on top of an array – Realtor

Answer 1

You would rarely use one in real life. I believe the purpose of the Fibonacci heap was to improve the asymptotic running time of Dijkstra's algorithm. It might give you an improvement for very, very large inputs, but most of the time, a simple binary heap is all you need.

From Wiki:

Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.

The binary heap is a data structure that can be used to quickly find the maximum (or minimum) value in a set of values. It's used in Dijkstra's algorithm (shortest path), Prim's algorithm (minimum spanning tree) and Huffman encoding (data compression).

Hurty

Note: Fibonacci improves the amortized time, not worst case. And the binary heap also has O(1) average. – Calpe

Answer 2

Can't say about the fibonacci heaps but binary heaps are used in the priority queues. Priority queues are widely used in the real systems.

One known example is process scheduling in the kernel. The highest priority process is taken first.

I have used the priority queues in the partitioning of the sets. The set which has the maximum members was to be taken first for the partitioning.

Rape

Answer 3

In most scenarios, you have to choose based on the complexity of:

• insertion
• finding elements

And the usual suspects are:

• BST: log(n) insert and find
• linked list: O(1) insert and O(n) find
• heap:
  • O(1) insert
    • average for binary heap, see: https://mcmap.net/q/15516/-heap-vs-binary-search-tree-bst)
    • amortized for Fibonacci. This is stronger than average, weaker than worst case.
  • O(1) find for the first element only, O(n) in general
    • worst case for the binary heap
    • amortized for Fibonacci

There is also the Brodal queue and other heaps which reach O(1) worst case, but requires even larger queues than Fibonacci to be worth it.

So if your algorithm only needs to "find" the first element and do lots of insertions, heaps are a good choice.

As others mentioned, this is the case for Dijkstra.

Calpe

Answer 4

Priority queues are usually implemented as heaps, for example: http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html

Computing the top N elements from a huge data-set can be done efficiently using binary heaps (e.g. top search queries in a large-scale website).

Ratite