Just like binary heaps, pairing heaps represent a priority queue and come in two varieties: max-pairing heap and min-pairing heap. Like before, we will discuss max-pairing heaps, and min-pairing heaps are analogous.
A pairing heap is a represented as a tree. In a max-pairing 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
In a pairing heap, the size operation is performed by maintaining and returning a variable that stores the number of elements in the tree.
Since the max element is in the root of the max tree, the
maxElementoperation simply returns the value of the root element.
meldoperation combines two valid max-pairing heap together into a single max-pairing heap.
To meld two max-trees, we compare the values at the roots and make the max-tree that has the smaller root the leftmost subtree of the other tree.
When we remove the root element of the tree, we are left with zero or more max-trees 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 max-tree, we have finished the melding process.
increaseKeyoperation 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 max-heap property is violated, so we “detach” the node (with its children) from the tree, and we are left with two max-trees that we need to meld to get a single max-tree.
To insert an element with value
kin a pairing heap, we create a new pairing heap with one node whose value is
k, and then we meld the single-node tree representing the new pairing heap with the tree representing the existing pairing heap.
Similarly to the
removeMaxElementoperations, we “detach” all nodes from the tree and then combine them by pairing them together until we are left with a single max-tree.