In this chapter, we will analyze the running time for several of the advanced data structures that have been presented in Chapters 4 and 6. In particular, we will consider the worst-case running time for any sequence of *m* operations. This contrasts with the more typical analysis, in which a worst-case bound is given for any *single* operation.

Analyze the binomial queue operations.

Introduce and analyze the Fibonacci heap.

This puzzle illustrates the point that sometimes it is easier to solve a problem indirectly than directly. The amortized analyses that we will perform will use this idea. We will introduce an extra variable, known as the *potential*, to allow us to prove results that seem very difficult to establish otherwise.

The first data structure we will look at is the binomial queue of Chapter 6, which we now review briefly. Recall that a *binomial tree B*_{0} is a one-node tree, and for *k* > 0, the binomial tree *B _{k}* is built by melding two binomial trees

The *rank* of a node in a binomial tree is equal to the number of children; in particular, the rank of the root of *B _{k}* is

The most important operation is *merge*. To merge two binomial queues, an operation similar to addition of binary integers is performed: At any stage we may have zero, one, two, or possibly three *B _{k}* trees, depending on whether or not the two priority queues contain a

Insertion is performed by creating a one-node binomial queue and performing a *merge*. The time to do this is *m* + 1, where *m* represents the smallest type of binomial tree *B _{m}* not present in the binomial queue. Thus, insertion into a binomial queue that has a

We consider a very simple problem first. Suppose we want to build a binomial queue of *n* elements. We know that building a binary heap of *n* elements can be done in *O *(*n*), so we expect a similar bound for binomial queues.

*A binomial queue of n elements can be built by n successive insertions in O*(*n*)* time.*

C_{1}+ (T_{1}-T_{0}) = 2

C_{2}+ (T_{2}-T_{1}) = 2

C-1 + (_{n}T-1 -_{n}T-2) = 2_{n}

C+ (_{n}T-_{n}T-1) = 2_{n}

If we add all these equations, most of the *T _{i}* terms cancel, leaving

This example illustrates the general technique we will use. The state of the data structure at any time is given by a function known as the *potential*. The potential function is not maintained by the program, but rather is an accounting device that will help with the analysis. When operations take less time than we have allocated for them, the unused time is "saved" in the form of a higher potential. In our example, the potential of the data structure is simply the number of trees. In the analysis above, when we have insertions that use only one unit instead of the two units that are allocated, the extra unit is saved for later by an increase in potential. When operations occur that exceed the allotted time, then the excess time is accounted for by a decrease in potential. One may view the potential as representing a savings account. If an operation uses less than its allotted time, the difference is saved for use later on by more expensive operations. Figure 11.4 shows the cumulative running time used by *build_binomial_queue* over a sequence of insertions. Observe that the running time never exceeds 2*n* and that the potential in the binomial queue after any insertion measures the amount of savings.

Once a potential function is chosen, we write the main equation:

*T*_{actual} + *Potential* = *T*_{amortized
}

Cancel a term in the actual time. In our case, if the actual cost was *c*, then the potential change was 2 - *c*. When these are added, an amortized cost of 2 is obtained. This is shown in Figure 11.5.

We can now perform a complete analysis of binomial queue operations.

The analysis of binomial queues is a fairly easy example of an amortized analysis. We now look at skew heaps. As is common with many of our examples, once the right potential function is found, the analysis is easy. The difficult part is choosing a meaningful potential function.

Recall that for skew heaps, the key operation is merging. To merge two skew heaps, we merge their right paths and make this the new left path. For each node on the new path, except the last, the old left subtree is attached as the right subtree. The last node on the new left path is known to not have a right subtree, so it is silly to give it one. The bound does not depend on this exception, and if the routine is coded recursively, this is what will happen naturally. Figure 11.6 shows the result of merging two skew heaps.

Suppose we have two heaps, *H*_{1} and *H*_{2}, and there are *r*_{1} and *r*_{2} nodes on their respective right paths. Then the actual time to perform the merge is proportional to *r*_{1} + *r*_{2}, so we will drop the Big-Oh notation and charge one unit of time for each node on the paths. Since the heaps have no structure, it is possible that all the nodes in both heaps lie on the right path, and this would give a (*n*) worst-case bound to merge the heaps (Exercise 11.3 asks you to construct an example). We will show that the amortized time to merge two skew heaps is *O*(log *n*).

As an example, Figure 11.7 shows a skew heap. The nodes with keys 15, 3, 6, 12, and 7 are heavy, and all other nodes are light.

The potential function we will use is the number of heavy nodes in the (collection) of heaps. This seems like a good choice, because a long right path will contain an inordinate number of heavy nodes. Because nodes on this path have their children swapped, these nodes will be converted to light nodes as a result of the merge.

*The amortized time to merge two skew heaps is* *O*(log *n*).

If we adopt the convention that the cost of merging two skew heaps is the total number of nodes on their right paths, then the actual time to perform the merge is *l*_{1}* + l*_{2}* + h*_{1}* + h*_{2.} 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 11.8.

If a heavy node is initially on the right path, then after the merge it must become a light node. The other nodes that were on the right path were light and may or may not become heavy, but since we are proving an upper bound, we will have to assume the worst, which is that they become heavy and increase the potential. Then the net change in the number of heavy nodes is at most *l*_{1}* + l*_{2}* - h*_{1}* - h*_{2.} Adding the actual time and the potential change (Equation 11.2) gives an amortized bound of 2(*l*_{1}* + l*_{2}).

Now we must show that *l*_{1}* + l*_{2} = *O*(log* n*). Since *l*_{1}* and l*_{2} are the number of light nodes on the original right paths, and the right subtree of a light node is less than half the size of the tree rooted at the light node, it follows directly that the number of light nodes on the right path is at most log *n*_{1}* + *log *n*_{2}, which is *O*(log* n*).

The proof is completed by noting that the initial potential is 0 and that the potential is always nonnegative. It is important to verify this, since otherwise the amortized time does not bound the actual time and is meaningless.

Since the *insert* and *delete_min* operations are basically just *merges*, they also have *O*(log* n*) amortized bounds.

In Section 9.3.2, we showed how to use priority queues to improve on the naïve *O*(|*V*|^{2}) running time of Dijkstra's shortest-path algorithm. The important observation was that the running time was dominated by|*E*|d*ecrease_key* operations and |*V*| *insert* and *delete_min* operations. These operations take place on a set of size at most |*V*|. By using a binary heap, all these operations take *O*(log |*V*|) time, so the resulting bound for Dijkstra's algorithm can be reduced to *O*(|*E*| log |*V*|).

In order to lower this time bound, the time required to perform the *decrease_key* operation must be improved. *d-*heaps, which were described in Section 6.5, give an *O*(log* _{d}* |

d= max(2,E/V).

This improves the time bound for Dijkstra's algorithm to

O(Elog_{(2+}_{E}_{/V}_{)}V).

The *Fibonacci heap* is a data structure that supports all the basic heap operations in *O*(1) amortized time, with the exception of *delete_min* and *delete*, which take *O* (log *n*) amortized time. It immediately follows that the heap operations in Dijkstra's algorithm will require a total of *O*(|*E*| + |*V*| log |*V*|) time.

Fibonacci heaps^{*} generalize binomial queues by adding two new concepts:

^{*}The name comes from a property of this data structure, which we will prove later in the section.

A *different implementation of decrease_key*: The method we have seen before is to percolate the element up toward the root. It does not seem reasonable to expect an *O*(1) amortized bound for this strategy, so a new method is needed.

*Lazy merging*: Two heaps are merged only when it is required to do so. This is similar to lazy deletion. For lazy merging, *merges* are cheap, but because lazy merging does not actually combine trees, the *delete_min* operation could encounter lots of trees, making that operation expensive. Any one *delete_min* could take linear time, but it is always possible to charge the time to previous *merge* operations. In particular, an expensive *delete_min* must have been preceded by a large number of unduly cheap *merges*, which have been able to store up extra potential.

In binary heaps, the *decrease_key* operation is implemented by lowering the value at a node and then percolating it up toward the root until heap order is established. In the worst case, this can take *O*(log *n*) time, which is the length of the longest path toward the root in a balanced tree.

This strategy does not work if the tree that represents the priority queue does not have *O*(log *n*) depth. As an example, if this strategy is applied to leftist heaps, then the *decrease_key* operation could take (*n*) time, as the example in Figure 11.9 shows.

We see that for leftist heaps, another strategy is needed for the *decrease_key* operation. Our example will be the leftist heap in Figure 11.10. Suppose we want to decrease the key with value 9 down to 0. If we make the change, we find that we have created a violation of heap order, which is indicated by a dashed line in Figure 11.11.

We do not want to percolate the 0 to the root, because, as we have seen, there are cases where this could be expensive. The solution is to *cut* the heap along the dashed line, thus creating two trees, and then merge the two trees back into one. Let *x* be the node to which the *decrease_key* operation is being applied, and let *p* be its parent. After the cut, we have two trees, namely, *H*_{1} with root *x*, and *T*_{2}, which is the original tree with *H*_{1} removed. The situation is shown in Figure 11.12.

If these two trees were both leftist heaps, then they could be merged in *O *(log *n*) time, and we would be done. It is easy to see that *H*_{1} is a leftist heap, since none of its nodes have had any changes in their descendants. Thus, since all of its nodes originally satisfied the leftist property, they still must.

Nevertheless, it seems that this scheme will not work, because *T*_{2} is not necessarily leftist. However, it is easy to reinstate the leftist heap property by using two observations:

Only nodes on the path from *p* to the root of *T*_{2} can be in violation of the leftist heap property; these can be fixed by swapping children.

Since the maximum right path length has at most log(*n* + 1) nodes, we only need to check the first log(*n* + 1) nodes on the path from *p* to the root of *T*_{2}. Figure 11.13 shows *H*_{1} and *T*_{2} after *T*_{2} is converted to a leftist heap.

Because we can convert *T*_{2} to the leftist heap *H*_{2} in *O *(log *n*) steps, and then merge *H*_{1} and *H*_{2}, we have an *O *(log *n*) algorithm for performing the *decrease_key* operation in leftist heaps. The heap that results in our example is shown in Figure 11.14.

The second idea that is used by Fibonacci heaps is *lazy merging*. We will apply this idea to binomial queues and show that the amortized time to perform a *merge* operation (as well as insertion, which is a special case) is *O*(1). The amortized time for *delete_min* will still be *O*(log *n*).

As an example, Figure 11.15 shows a lazy binomial queue. In a lazy binomial queue, there can be more than one tree of the same size. We can tell the size of a tree by examining the root's *rank* field, which gives the number of children (and thus implicitly the type of tree). To perform the *delete_min*, we remove the smallest element, as before, and obtain the tree in Figure 11.16.

We now have to merge all the trees and obtain a standard binomial queue. A standard binomial queue has at most one tree of each rank. In order to do this efficiently, we must be able to perform the *merge* in time proportional to the number of trees present (*T*) (or log *n*, whichever is larger). To do this, we form an array of lists, *L*_{0},* L*_{1}, . . . , *L _{R}*max

Each time through the loop, at lines 3 through 5, the total number of trees is reduced by 1. This means that this part of the code, which takes constant time per execution, can only be performed *T* - 1 times, where *T* is the number of trees. The *for* loop counters, and tests at the end of the *while* loop take *O *(log *n*) time, so the running time is *O* (*T* + log *n*), as required. Figure 11.18 shows the execution of this algorithm on the previous collection of binomial trees.

Amortized Analysis of Lazy Binomial Queues

/*1*/ for( r = 0; r <= logn; r++ )

/*2*/ while ( |L| 2 )_{r}

{

/*3*/ remove two trees fromL;_{r}

/*4*/ merge the two trees into a new tree;

/*5*/ add the new tree toL+1 ;_{r}

}

For the *merge* operation, the actual time is constant, and the number of trees in the collection of binomial queues is unchanged, so, by Equation (11.2), the amortized time is *O*(1).

For the *insert* operation, the actual time is constant, and the number of trees can increase by at most 1, so the amortized time is *O*(1).

The *delete_min* operation is more complicated. Let *r* be the rank of the tree that contains the minimum element, and let *T* be the number of trees. Thus, the potential at the start of the *delete_min* operation is *T*. To perform a *delete_min,* the children of the smallest node are split off into separate trees. This creates *T* + *r* trees, which must be merged into a standard binomial queue. The actual time to perform this is *T* + *r* + log *n*, if we ignore the constant in the Big-Oh notation, by the argument above.^{*} On the other hand, once this is done, there can be at most log *n* trees remaining, so the potential function can increase by at most (log *n*) - *T*. Adding the actual time and the change in potential gives an amortized bound of 2 log *n* + *r*. Since all the trees are binomial trees, we know that r log *n*. Thus we arrive at an* O*(log *n*) amortized time bound for the *delete_min* operation.

^{*}We can do this because we can place the constant implied by the Big-Oh notation in the potential function and still get the cancellation of terms, which is needed in the proof.

As we mentioned before, the Fibonacci heap combines the leftist heap *decrease_key* operation with the lazy binomial queue *merge* operation. Unfortunately, we cannot use both operations without a slight modification. The problem is that if arbitrary cuts are made in the binomial trees, the resulting forest will no longer be a collection of binomial trees. Because of this, it will no longer be true that the rank of every tree is at most log *n*. Since the amortized bound for *delete_min* in lazy binomial queues was shown to be 2 log *n* + *r*, we need *r* = *O*(log *n*) for the *delete_min* bound to hold.

In order to ensure that *r* = *O*(log *n*), we apply the following rules to all non-root nodes:

Mark a (nonroot) node the first time that it loses a child (because of a cut).

If a marked node loses another child, then cut it from its parent. This node now becomes the root of a separate tree and is no longer marked. This is called a *cascading cut*, because several of these could occur in one *decrease_key* operation.

Figure 11.19 shows one tree in a Fibonacci heap prior to a *decrease_key *operation.

When the node with key 39 is changed to 12, the heap order is violated. Therefore, the node is cut from its parent, becoming the root of a new tree. Since the node containing 33 is marked, this is its second lost child, and thus it is cut from its parent (10). Now 10 has lost its second child, so it is cut from 5. The process stops here, since 5 was unmarked. 5 is now marked. The result is shown in Figure 11.20.

Notice that 10 and 33, which used to be marked nodes, are no longer marked, because they are now root nodes. This will be a crucial observation in our proof of the time bound.

From Lemma 11.1, it is easy to show that any node of rank *r* must have a lot of descendants.

*Let F _{k} be the Fibonacci numbers defined (in *

PROOF:

Let *S _{r}* be the smallest tree of rank

Because it is well known that the Fibonacci numbers grow exponentially, it immediately follows that any node with *s* descendants has rank at most *O*(log *s*). Thus, we have

*The rank of any node in a Fibonacci heap is O*(log *n*)*.*

Immediate from the discussion above.

The actual time required for a *decrease_key* operation is 1 plus the number of cascading cuts that are performed during the operation. Since the number of cascading cuts could be much more than *O*(1), we will need to pay for this with a loss in potential. If we look at Figure 11.20, we see that the number of trees actually increases with each cascading cut, so we will have to enhance the potential function to include something that decreases during cascading cuts. Notice that we cannot just throw out the number of trees from the potential function, since then we will not be able to prove the time bound for the *merge* operation. Looking at Figure 11.20 again, we see that a cascading cut causes a decrease in the number of marked nodes, because each node that is the victim of a cascading cut becomes an unmarked root. Since each cascading cut costs 1 unit of actual time and increases the tree potential by 1, we will count each marked node as two units of potential. This way, we have a chance of canceling out the number of cascading cuts.

For the *merge* operation, the actual time is constant, and the number of trees and marked nodes is unchanged, so, by Equation (11.2), the amortized time is *O*(1).

For the *insert* operation, the actual time is constant, the number of trees increases by 1, and the number of marked nodes is unchanged. Thus, the potential increases by at most 1, so the amortized time is *O*(1).

For the *delete_min* operation, let *r* be the rank of the tree that contains the minimum element, and let *T* be the number of trees before the operation. To perform a *delete_min*, we once again split the children of a tree, creating an additional *r* new trees. Notice that, although this can remove marked nodes (by making them unmarked roots), this cannot create any additional marked nodes. These *r* new trees, along with the other *T* trees, must now be merged, at a cost of *T* + *r* + log *n* = *T* + *O*(log *n*), by Lemma 11.3. Since there can be at most *O*(log *n*) trees, and the number of marked nodes cannot increase, the potential change is at most *O*(log *n*) - *T*. Adding the actual time and potential change gives the *O*(log *n*) amortized bound for *delete_min*.

Finally, for the *decrease_key* operation, let *C* be the number of cascading cuts. The actual cost of a *decrease_key* is *C* + 1, which is the total number of cuts performed. The first (noncascading) cut creates a new tree and thus increases the potential by 1. Each cascading cut creates a new tree, but converts a marked node to an unmarked (root) node, for a net loss of one unit per cascading cut. The last cut also can convert an unmarked node (in Figure 11.20 it is node *5*) into a marked node, thus increasing the potential by 2. The total change in potential is thus 3 - *C*. Adding the actual time and the potential change gives a total of 4, which is *O *(1).

As a final example, we analyze the running time of splay trees. Recall, from Chapter 4, that after an access of some item *x* is** **performed, a splaying step moves *x* to the root by a series of three operations: *zig, zig-zag*, and *zig-zig*. These tree rotations are shown in Figure 11.21. We adopt the convention that if a tree rotation is being performed at node *x*, then prior to the rotation *p* is its parent and *g* is its grandparent (if *x* is not the child of the root).

Recall that the time required for any tree operation on node *x* is proportional to the number of nodes on the path from the root to *x.* If we count each *zig* operation as one rotation and each *zig-zig* or *zig-zag* as two rotations, then the cost of any access is equal to 1 plus the number of rotations.

In order to show an *O*(log *n*) amortized bound for the splaying step, we need a potential function which can increase by at most *O*(log *n*) over the entire splaying step, but which will also cancel out the number of rotations performed during the step. It is not at all easy to find a potential function that satisfies these criteria. A simple first guess at a potential function might be the sum of the depths of all the nodes in the tree. This does not work, because the potential can increase by (*n*) during an access. A canonical example of this occurs when elements are inserted in sequential order.

A potential function , which does work, is defined as

*S*(*i*) represents the number of descendants of *i* (including *i* itself). The potential function is the sum, over all nodes *i* in the tree *T*, of the logarithm of *S*(*i*).

To simplify the notation, we will define

R(i) = logS(i).

Before proving the main theorem, we need the following lemma.

*If a + b ** c, and a and b are both positive integers, then*

By the arithmetic-geometric mean inequality,

abc^{2}/4

Taking logarithms of both sides proves the lemma.

With the preliminaries taken care of, we are ready to prove the main theorem.

*The amortized time to splay a tree with root T at node x is at most* 3(*R*(*T*) *- R*(*x*))* + *1* *=* O*(log* n*)*.*

The potential function is the sum of the ranks of the nodes in *T*.

For any splaying step, let *R _{i}*(

AT_{zig}= 1 +R(_{f}x) +R(_{f}p) -R(_{i}x) -R(_{i}p)

From Figure 11.21 we see that *S _{i}*(

AT_{zig}1 +R(_{f}x) -R(_{i}x).

Since *S _{f}*(

AT_{zig}1 + 3(R(_{f}x) -R(_{i}x)).

*Zig-zag step:* For the *zig-zag* case, the actual cost is 2, and the potential change is *R _{f}*(

AT_{zig-zag}= 2 +R(_{f}x) +R(_{f}p) +R(_{f}g) -R(_{i}x) -R(_{i}p) -R(_{i}g).

From Figure 11.21 we see that *S _{f}*(

AT_{zig-zag}= 2 +R(_{f}p) +R(_{f}g)- R(_{i}x)- R(_{i}p).

We also see that *S _{i}*(

AT_{zig-zag}2 +R(_{f}p) +R(_{f}g) - 2R(_{i}x).

From Figure 11.21 we see that *S _{f}*(

logS(_{f}p) + logS(_{f}g) 2 logS(_{f}x) - 2.

By definition of *rank*, this becomes

R(_{f}p) +R(_{f}g) 2R(_{f}x) - 2.

Substituting this we obtain

AT_{zig-zag}2R(_{f}x) - 2R(_{i}x)

2(R(_{f}x) -R(_{i}x))

Since *R _{f}*(

AT_{zig-zag}3(R(_{f}x) -R(_{i}x)).

*Zig-zig step:* The third case is the *zig-zig*. The proof of this case is very similar to the *zig-zag* case. The important inequalities are *R _{f}*(

The amortized cost of an entire splay is the sum of the amortized costs of each splay step. Figure 11.22 shows the steps which are performed in a splay at node 2. Let *R*_{1}* *(2),* R*_{2}(2),* R*_{3}(2), and *R*_{4}(2) be the rank of node 2 in each of the four trees. The cost of the first step, which is a *zig-zag*, is at most 3(*R*_{2}(2) - *R*_{1} (2)). The cost of the second step, which is a *zig-zig*, is 3(*R*_{3}(2) - *R*_{2}(2)). The last step is a *zig* and has a cost no larger than 3(*R*_{4}(2) - *R*_{3}(2)) + 1. The total cost thus telescopes to 3(*R*_{4}(2) - *R*_{1}(2)) + 1.

In general, by adding up the amortized costs of all the rotations, of which at most one can be a *zig*, we see that the total amortized cost to splay at node *x* is at most 3(*R _{f}*(

As expressed by Equation (11.2), the amortized time for an operation is equal to the sum of the actual time and potential change. Taken over an entire sequence of operations, the amortized time for the sequence is equal to the total sequence time plus the net change in potential. As long as this net change is positive, then the amortized bound provides an *upper bound* for the actual time spent and is meaningful.

The keys to choosing a potential function are to guarantee that the minimum potential occurs at the beginning of the algorithm, and to have the potential increase for cheap operations and decrease for expensive operations. It is important that the excess or saved time be measured by an opposite change in potential. Unfortunately, this is sometimes easier said than done.

11.1 When do m consecutive insertions into a binomial queue take less than 2m time units?

11.2 Suppose a binomial queue of n = 2^{k - 1} elements is built. Alternately perform m insert and delete_min pairs. Clearly, each operation takes O(log n) time. Why does this not contradict the amortized bound of O(1) for insertion?

*11.3 Show that the amortized bound of O(log n) for the skew heap operations described in the text cannot be converted to a worst-case bound, by giving a sequence of operations that lead to a merge requiring (n) time.

*11.4 Show how to merge two skew heaps with one top-down pass and reduce the merge cost to O(1) amortized time.

11.5 Extend skew heaps to support the decrease_key operation in O(log n) amortized time.

11.6 Implement Fibonacci heaps and compare their performance with binary heaps when used in Dijkstra's algorithm.

11.7 A standard implementation of Fibonacci heaps requires four pointers per node (parent, child, and two siblings). Show how to reduce the number of pointers, at the cost of at most a constant factor in the running time.

11.8 Show that the amortized time of a zig-zig splay is at most 3(R_{f}(x) - R_{i}(x)).

11.9 By changing the potential function, it is possible to prove different bounds for splaying. Let the weight function W(i) be some function assigned to each node in the tree, and let S(i) be the sum of the weights of all the nodes in the subtree rooted at i, including i itself. The special case W(i) = 1 for all nodes corresponds to the function used in the proof of the splaying bound. Let n be the number of nodes in the tree, and let m be the number of accesses. Prove the following two theorems:

a. The total access time is O(m + (m + n)log n).

11.10 a. Show how to implement the merge operation on splay trees so that a sequence of n -1 merges starting from n single-element trees takes O(n log^{2} n) time.

*b. Improve the bound to O(n log n).

11.11 In Chapter 5, we described rehasing: When a table becomes more than half full, a new table twice as large is constructed, and the entire old table is rehashed. Give a formal amortized analysis, with potential function, to show that the amortized cost of an insertion is still O(1).

11.12 Show that if deletions are not allowed, then any sequence of m insertions into an n node 2-3 tree produces O(m + n) node splits.

11.13 A deque with heap order is a data structure consisting of a list of items, on which the following operations are possible:

*push(x,d): *Insert item *x* on the front end of deque *d*.

*pop(d):* Remove the front item from deque *d* and return it.

*inject(x,d): *Insert item *x* on the rear end of deque *d*.

*eject(d):* Remove the rear item from deque *d* and return it.

*find _min(d): *Return the smallest item from deque *d* (breaking ties arbitrarily).

a. Describe how to support these operations in constant amortized time per operation.

**b. Describe how to support these operations in constant worst-case time per operation.

An excellent survey of amortized analysis is provided in [9].

Most of the references below duplicate citations in earlier chapters. We cite them again for convenience and completeness. Binomial queues were first described in [10] and analyzed in [1]. Solutions to 11.3 and 11.4 appear in [8]. Fibonacci heaps are described in [3]. Exercise 11.9a shows that splay trees are optimal, to within a constant factor of the the best static search trees. 11.9b shows that splay trees are optimal, to within a constant factor of the best optimal search trees. These, as well as two other strong results, are proved in the original splay tree paper [6].

The *merge* operation for splay trees is described in [5]. Exercise 11.12 is solved, with an implicit use of amortization, in [2]. The paper also shows how to merge 2-3 trees efficiently. A solution to 11.13 can be found in [4].

Amortized analysis is used in [7] to design an on-line algorithm that processes a series of queries in time only a constant factor larger than any off-line algorithm in its class.

1. M. R. Brown, "Implementation and Analysis of Binomial Queue Algorithms," *SIAM Journal on Computing* 7 (1978), 298-319.

2. M. R. Brown and R. E. Tarjan, "Design and Analysis of a Data Structure for Representing Sorted Lists," *SIAM Journal on Computing* 9 (1980), 594-614.

3. M. L. Fredman and R. E. Tarjan, "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms," *Journal of the ACM* 34 (1987), 596-615.

4. H. Gajewska and R. E. Tarjan, "Deques with Heap Order," *Information Processing Letters* 22 (1986), 197-200.

5. G. Port and A. Moffat, "A Fast Algorithm for Melding Splay Trees," *Proceedings of the First Workshop on Algorithms and Data Structures*, 1989, 450-459.

6. D. D. Sleator and R. E. Tarjan, "Self-adjusting Binary Search Trees," *Journal of the ACM *32 (1985), 652-686.

7. D. D. Sleator and R. E. Tarjan, "Amortized Efficiency of List Update and Paging Rules," *Communications of the ACM* 28 (1985), 202-208.

8. D. D. Sleator and R. E. Tarjan, "Self-adjusting Heaps," *SIAM Journal on Computing *15 (1986), 52-69.

9. R. E. Tarjan, "Amortized Computational Complexity," *SIAM Journal on Algebraic and Discrete Methods* 6 (1985), 306-318.

10. J. Vuillemin, "A Data Structure for Manipulating Priority Queues," *Communications of the ACM* 21 (1978), 309-314.