1. Show that the binomial queues actually support merging in O(1) amortized time. De?ne the potential of a binomial queue to be the number of trees plus the rank of the largest tree.
2. Suppose that in an attempt to save time, we splay on every second tree operation. Does the amortized cost remain logarithmic?
3. Using the potential function in the proof of the splay tree bound, what is the maximum and minimum potential of a splay tree? By how much can the potential function decrease in one splay? By how much can the potential function increase in one splay? You may give Big-Oh answers.