advanced data structures and implementation pairing heaps the last data structure we examine is the pairing heap the analysis of the pairing heap is still openbut when decreasekey operations are neededit seems to outperform other heap structures the most likely reason for its efficiency is its simplicity the pairing heap is represented as heap-ordered tree figure shows sample pairing heap the actual pairing heap implementation uses left childright sibling representation as discussed in the decreasekey operationas we will seerequires that each node contain an additional link node that is leftmost child contains link to its parentotherwise the node is right sibling and contains link to its left sibling we'll refer to this data member as prev the class skeleton and pairing heap node declaration are omitted for brevitythey are completely straightforward figure shows the actual representation of the pairing heap in figure we begin by sketching the basic operations to merge two pairing heapswe make the heap with the larger root left child of the heap with the smaller root insertion isof coursea special case of merging to perform decreasekeywe lower the value in the requested node because we are not maintaining parent pointers for all nodeswe figure sample pairing heapabstract representation figure actual representation of previous pairing heap