figure change in heavy/light status after merge proof let and be the two heapswith and nodesrespectively suppose the right path of has light nodes and heavy nodesfor total of likewiseh has light and heavy nodes on its right pathfor total of nodes if we adopt the convention that the cost of merging two skew heaps is the total number of nodes on their right pathsthen the actual time to perform the merge is now the only nodes whose heavy/light status can change are nodes that are initially on the right path (and wind up on the left path)since no other nodes have their subtrees altered this is shown by the example in figure if heavy node is initially on the right paththen after the merge it must become light node the other nodes that were on the right path were light and may or may not become heavybut since we are proving an upper boundwe will have to assume the worstwhich is that they become heavy and increase the potential then the net change in the number of heavy nodes is at most adding the actual time and the potential change [equation ( )gives an amortized bound of ( + now we must show that (log nsince and are the number of light nodes on the original right pathsand the right subtree of light node is less than half the size of the tree rooted at the light nodeit follows directly that the number of light nodes on the right path is at most log log which is (log nthe proof is completed by noting that the initial potential is and that the potential is always nonnegative it is important to verify thissince otherwise the amortized time does not bound the actual time and is meaningless since the insert and deletemin operations are basically just mergesthey also have (log namortized bounds fibonacci heaps in section we showed how to use priority queues to improve on the naive (| | running time of dijkstra' shortest-path algorithm the important observation was that the running time was dominated by |edecreasekey operations and |vinsert and deletemin operations these operations take place on set of size at most |vby using binary heapall these operations take (log | |timeso the resulting bound for dijkstra' algorithm can be reduced to (|elog | |