amortized analysis figure the two trees after the cut we do not want to percolate the to the rootbecauseas we have seenthere are cases where this could be expensive the solution is to cut the heap along the dashed linethus creating two treesand then merge the two trees back into one let be the node to which the decreasekey operation is being appliedand let be its parent after the cutwe have two treesnamelyh with root xand which is the original tree with removed the situation is shown in figure if these two trees were both leftist heapsthen they could be merged in (log ntimeand we would be done it is easy to see that is leftist heapsince none of its nodes have had any changes in their descendants thussince all of its nodes originally satisfied the leftist propertythey still must neverthelessit seems that this scheme will not workbecause is not necessarily leftist howeverit is easy to reinstate the leftist heap property by using two observationsr only nodes on the path from to the root of can be in violation of the leftist heap propertythese can be fixed by swapping children since the maximum right path length has at most log( nodeswe only need to check the first log( nodes on the path from to the root of figure shows and after is converted to leftist heap because we can convert to the leftist heap in (log nstepsand then merge and we have an (log nalgorithm for performing the decreasekey operation in leftist heaps the heap that results in our example is shown in figure lazy merging for binomial queues the second idea that is used by fibonacci heaps is lazy merging we will apply this idea to binomial queues and show that the amortized time to perform merge operation (as well as insertionwhich is special caseis ( the amortized time for deletemin will still be (log nthe idea is as followsto merge two binomial queuesmerely concatenate the two lists of binomial treescreating new binomial queue this new queue may have several trees of