Binary Heap | Binomial Heap | Fibonacci Heap (M5)

Binary Heap

A Binary Heap is a Binary Tree with following properties.

1. It’s a complete binary tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2. A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to Min Heap.

 
A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.

A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent. Every node in a binary tree has a left and right reference along with the data element. The node at the top of the hierarchy of a tree is called the root node. The nodes that hold other sub-nodes are the parent nodes.

 Binomial Heap

A Binomial Heap is a collection of Binomial Tree where each Binomial Tree follows the Min-Heap property and there can be at most one Binomial Tree of any degree.

The binomial tree Bk is an ordered tree defined recursively, the binomial tree B0 consists of a single node. The binomial tree Bk consists of two binomial trees Bk -1 that are linked together so that the root of one is the leftmost child of the root of the other.

Fibonacci Heap

A Fibonacci heap is a specific implementation of the heap data structure that makes use of Fibonacci numbers. Like Binomial Heap, Fibonacci Heap is a collection of trees with Min-Heap or Max-Heap property. 

In Fibonacci Heap, trees can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be a Binomial Tree). 

 Fibonacci Heap maintains a pointer to a minimum value (which is the root of a tree). All tree roots are connected using a circular doubly linked list, so all of them can be accessed using a single ‘min’ pointer.

Like binomial heaps, Fibonacci heaps use doubly linked lists to allow for $O(1)$ time for operations such as splicing off a part of a list, merging two lists, and finding the minimum (or maximum) value. Each node contains a pointer to its parent and any one of its children. The children are all linked together in a doubly linked list called the child list. Each child in the child list has pointers for its left sibling and its right sibling.

For each node, the linked list also maintains the number of children a node has, a pointer to the root containing the minimum key, and whether the node is marked. A node is marked to indicate that it has lost a single child and a node is unmarked if it loses no children. See the description of the decrease-key function in the next section for more details. 

Advantages:

Fibonacci heaps are used to implement the priority queue element in Dijkstra’s algorithm, giving the algorithm a very efficient running time. 

Fibonacci heaps have a faster amortized running time than other heap types. Fibonacci heaps are similar to binomial heaps but Fibonacci heaps have a less rigid structure. 

Binomial heaps merge heaps immediately but Fibonacci heaps wait to merge until the extract-min function is called.

 

 https://brilliant.org/wiki/fibonacci-heap/

https://brilliant.org/wiki/binomial-heap/