advanced data structures and implementation /*internal method that is the basic operation to maintain order links first and second together to satisfy heap order first is root of tree which may not be nullptr first->nextsibling must be nullptr on entry second is root of tree which may be nullptr first becomes the result of the tree merge *void compareandlinkpairnode firstpairnode *second ifsecond =nullptr returnifsecond->element element /attach first as leftmost child of second second->prev first->prevfirst->prev secondfirst->nextsibling second->leftchildiffirst->nextsibling !nullptr first->nextsibling->prev firstsecond->leftchild firstfirst secondelse /attach second as leftmost child of first second->prev firstfirst->nextsibling second->nextsiblingiffirst->nextsibling !nullptr first->nextsibling->prev firstsecond->nextsibling first->leftchildifsecond->nextsibling !nullptr second->nextsibling->prev secondfirst->leftchild secondfigure pairing heapsroutine to merge two subheaps children after the first scanwe have half as many trees to merge second scan is then performedright to left at each step we merge the rightmost tree remaining from the first we must be careful if there is an odd number of children when that happenswe merge the last child with the result of the rightmost merge to complete the first scan