125. Introducing the Pairing Heap data structure
The Pairing Heap is a flavor of Binomial Heap with the capability of self-adjusting/rearranging to keep itself balanced. It has very good performance in amortized time and is a good fit for the task of implementing priority queues.
A Pairing Heap is a pairing tree with a root and children. Each heap of a Pairing Heap represents a value and has a set of children that are also heaps. The value of a heap is always less than (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.40: 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...
