1. If some values are much more frequently inserted than others, or if the insertion sequence has some locality of reference (each insertion is likely to have a priority close to that of the most recent previous insertion), then the splay tree may take less than logarithmic time per insertion and deletion, whereas (if n items are inserted and then some time later deleted) the Fibonacci heap will take O(log n) time per item. So the splay tree could be faster than the Fibonacci heap, especially if decrease-key operations are not used. 2. (a) In each node, store the number of descendants (including itself). Then, to find the kth largest value: if k is at most equal to the number of descendants stored in the right child, branch rightwards, if it is that number plus one, return the current node, and otherwise subtract the number of right descendants from k and branch leftward. In this way one can perform a binary search for the kth node in constant time per step. (b) When rotating x and y (where x was the child of y before the rotation, and x is the parent of y after the rotation): the new number of descendants of x is the same as the old number of descendants of y. The new number of descendants of y is one plus the sum of the numbers stored at its two new children. 3. (a) Yes, if the heap is stored as a tree with an explicit object for each node: the tree is only accessed by paths from a single node, the root, so node-copying works. If the heap is stored as an array, though, node-copying doesn't work (unless you think of the whole array as one big node, in which case it's very inefficient). (b) Yes. Each operation follows a short path from a tree root so only that path needs to be copied. (c) No. Because the Fibonacci heap is an amortized data structure, with operations that may have large worst case time bounds, node copying could be very inefficient. 4. (a) O(n). There may be as many as n different sets (each item could be in a different set prior to the operation). (b) If an operation moves k items to a new set, then the terms in the potential function for the previously existing sets may increase (become less negative) by |S_i|/sqrt n per set; in the worst case, these terms include all of the sets in the structure, so the total increase is (sum |S_i|)/sqrt n = n/sqrt n = sqrt n. On the other hand, the new set itself causes the potential function to decrease by k^2/sqrt n. Thus, the total change to the potential function is sqrt n - k^2/sqrt n or something smaller than that. If k <= sqrt n, then the potential function increases by at most sqrt n, and the actual time of the operation is O(sqrt n), so the amortized time is O(sqrt n). If k >= sqrt n, then k^2/sqrt n >= k, and the change to the potential function is at most sqrt n - k. The "-k" part of this cancels the O(k) actual time for the operation, leaving O(sqrt n) amortized time.