figure compareandlink merges two subheaps don' know if this violates the heap order thus we cut the adjusted node from its parent and complete the decreasekey by merging the two heaps that result to perform deleteminwe remove the rootcreating collection of heaps if there are children of the rootthen calls to the merge procedure will reassemble the heap the most important detail is the method used to perform the merge and how the merges are applied figure shows how two subheaps are combined the procedure is generalized to allow the second subheap to have siblings as we mentioned earlierthe subheap with the larger root is made leftmost child of the other subheap the code is straightforward and shown in figure notice that we have several instances in which pointer is tested against nullptr before assigning its prev data memberthis suggests that perhaps it would be useful to have nullnode sentinelwhich was customary in this search tree implementations the insert and decreasekey operations arethensimple implementations of the abstract description decreasekey requires position objectwhich is just pairnodesince this is determined (irrevocablywhen an item is first insertedinsert returns the pointer to pairnode it allocates back to the caller the code is shown in figure our routine for decreasekey throws an exception if the new value is not smaller than the oldotherwisethe resulting structure might not obey heap order the basic deletemin procedure follows directly from the abstract description and is shown in figure the devilof courseis in the detailshow is combinesiblings implementedseveral variants have been proposedbut none has been shown to provide the same amortized bounds as the fibonacci heap it has recently been shown that almost all of the proposed methods are in fact theoretically less efficient than the fibonacci heap even sothe method coded in figure on page always seems to perform as well as or better than other heap structuresincluding the binary heapfor the typical graph theory uses that involve host of decreasekey operations this methodknown as two-pass mergingis the simplest and most practical of the many variants that have been suggested we first scan left to rightmerging pairs of