Introducing the Fibonacci Heaps data structure – Arrays, collections and data structures
117. Introducing the Fibonacci Heaps data structure
A Fibonacci Heap is a flavor of Binomial Heap with excellent performance in amortized time for operations such as insert, extract minimum and merge. It is an optimal choice for implementing priority queues. A Fibonacci Heap is made of trees, and each tree has a single root and multiple children arranged in a heap-ordered fashion. The root node with the smallest key is always placed at the beginning of the list of trees.
It is called a Fibonacci Heap because each tree of order k has at least Fk+2 nodes, where Fk+2 is the (k+2)th Fibonacci number.
In the following figure, you can see a Fibonacci Heap sample:
Figure 5.39 – Fibonacci Heap sample
The main operations in a Fibonacci Heap are (Big O represents the amortized time): insert (O(1)), decrease key (O(1)), find the minimum (O(1)), extract minimum (O(log n)), deletion (O(log n)), and merge (O(1)). You can find an implementation of these operations in the bundled code.
118. Introducing the Pairing Heaps data structure
The Pairing Heaps is a flavor of Binomial Heap with the capability of self-adjusting/rearranging for preserving itself balanced. It has very good performance in amortized time and fits very well for implementing priority queues.A Pairing Heap is a Pairing Tree having a root and children. Each heap of a Pairing Heap represents a value and has a set of children being also heaps. The value of a heap is always less (min-heap property) or greater than (max-heap property) the value of its children heaps.In the following figure you can see a Min Pairing Heap:
Figure 5.38 – A Min Pairing Heap sample
The main operations in a Pairing Heap are: insert (O(1)), decrease key (actual time: O(1), amortized time O(log n)), find the minimum (O(1)), extract the minimum (actual time: O(n), amortized time (O (log n)), and merge (actual time: O(1), amortized time (O(log n)). You can find an implementation of these operations in the bundled code.