Pairing Heap

Just like binary heaps, pairing heaps represent a priority queue and come in two varieties: maxpairing heap and minpairing heap. Like before, we will discuss maxpairing heaps, and minpairing heaps are analogous.

A pairing heap is a represented as a tree. In a maxpairing heap, each node’s value is greater than or equal to those of its children. It is not a binary tree, so a node can have any number of children.
Pairing Heap Operations
size

In a pairing heap, the size operation is performed by maintaining and returning a variable that stores the number of elements in the tree.
maxElement

Since the max element is in the root of the max tree, the
maxElement
operation simply returns the value of the root element.
meld

The
meld
operation combines two valid maxpairing heap together into a single maxpairing heap. 
To meld two maxtrees, we compare the values at the roots and make the maxtree that has the smaller root the leftmost subtree of the other tree.
removeMaxElement

When we remove the root element of the tree, we are left with zero or more maxtrees that were the root’s children.

If the root of the tree did not have any children, the pairing heap is now empty.

Otherwise, we combine the old root’s children into a single pairing heap tree by we first putting them in a FIFO queue. Then we take pairs of trees from the front of the queue, meld them and put the resulting tree at the end of the queue. Once we are left with just one maxtree, we have finished the melding process.
increaseKey

The
increaseKey
operation increases the value of a node’s key. If the new value is less than or equal to that of the parent, no work needs to be done. Otherwise, the maxheap property is violated, so we “detach” the node (with its children) from the tree, and we are left with two maxtrees that we need to meld to get a single maxtree.
insert

To insert an element with value
k
in a pairing heap, we create a new pairing heap with one node whose value isk
, and then we meld the singlenode tree representing the new pairing heap with the tree representing the existing pairing heap.
updatePriorities

Similarly to the
increaseKey
andremoveMaxElement
operations, we “detach” all nodes from the tree and then combine them by pairing them together until we are left with a single maxtree.