CHAPTER 11
Amortized Analysis
11.2 Although each insertion takes roughly log N, and each deleteMin takes 2 log N actual time, our accounting
11.3 Insert the sequence N, N + 1, N−1, N + 2, N−2, N + 3, . . . , 1, 2N into an initially empty skew heap. The right
11.5 We implement decreaseKey(x) as follows: If lowering the value of x creates a heap order violation, then cut x
11.8 For the zig-zig case, the actual cost is 2, and the potential change is Rf (X) + Rf (P) + Rf (G)− Ri (X)−Ri (P)−Ri
(G). This gives an amortized time bound of
11.9 (a) Choose W(i) = 1/N for each item. Then for any access of node X, Rf (X) = 0, and Ri (X) −log N, so the
11.10 (a) To merge two splay trees T1 and T2, we access each node in the smaller tree and insert it into the larger
tree. Each time a node is accessed, it joins a tree that is at least twice as large; thus a node can be inserted log
(b) Port and Moffet [6] suggest the following algorithm: If T2 is the smaller tree, insert its root into T1. Then
11.11 The potential function is c times the number of insertions since the last rehashing step, where c is a constant.
For an insertion that doesn’t require rehashing, the actual time is 1, and the potential increases by c, for a cost
of 1 + c.
11.12 We can (inductively) take a Fibonacci heap consisting of a single degenerate tree that extends as deep as
possible. Insert three very small items; do a deleteMin to force a merge. This leaves two of the newer small
11.13 (a) This problem is similar to Exercise 3.25. The first four operations are easy to implement by placing two
stacks, SL and SR , next to each other (with bottoms touching). We can implement the fifth operation by using
two more stacks, ML and MR (which hold minimums).
These operations don’t work if either SL or SR is empty. If a pop or eject is attempted on an empty stack, then
we clear ML and MR. We then redistribute the elements so that half are in SL and the rest in SR, and adjust ML
Define the potential function to be the absolute value of the number of elements in SL minus the number
of elements in SR. Any operation that doesn’t empty SL or SR can increase the potential by only 1; since the
11.16 The maximum potential is O(N log N) for a splay tree of maximum depth. The minimum potential is O(N) for