amortized analysis an unrelated puzzle consider the following puzzletwo kittens are placed on opposite ends of football field yards apart they walk toward each other at the speed of yards per minute at the same timetheir mother is at one end of the field she can run at yards per minute the mother runs from one kitten to the othermaking turns with no loss of speeduntil the kittens (and thus the mothermeet at midfield how far does the mother runit is not hard to solve this puzzle with brute-force calculation we leave the details to youbut one expects that this calculation will involve computing the sum of an infinite geometric series although this straightforward calculation will lead to an answerit turns out that much simpler solution can be arrived at by introducing an extra variablenamelytime because the kittens are yards apart and approach each other at combined velocity of yards per minuteit takes them five minutes to get to midfield since the mother runs yards per minuteher total is yards this puzzle illustrates the point that sometimes it is easier to solve problem indirectly than directly the amortized analyses that we will perform will use this idea we will introduce an extra variableknown as the potentialto allow us to prove results that seem very difficult to establish otherwise binomial queues the first data structure we will look at is the binomial queue of which we now review briefly recall that binomial tree is one-node treeand for the binomial tree bk is built by melding two binomial trees bk- together binomial trees through are shown in figure the rank of node in binomial tree is equal to the number of childrenin particularthe rank of the root of bk is binomial queue is collection of heap-ordered binomial trees in which there can be at most one binomial tree bk for any two binomial queuesh and are shown in figure the most important operation is merge to merge two binomial queuesan operation similar to addition of binary integers is performedat any stage we may have zeroonetwoor possibly three bk treesdepending on whether or not the two priority queues contain bk tree and whether or not bk tree is carried over from the previous step if there is zero or one bk treeit is placed as tree in the resultant binomial queue if there are two bk treesthey are melded into bk+ tree and carried overif there are three bk treesone is placed as tree in the binomial queue and the other two are melded and carried over the result of merging and is shown in figure insertion is performed by creating one-node binomial queue and performing merge the time to do this is where represents the smallest type of binomial tree bm not present in the binomial queue thusinsertion into binomial queue that has tree but no tree requires two steps deletion of the minimum is accomplished by removing the