Fundamentals of Amortization

Prev: Lazy Evaluation Next: Amortization and Persistence via Lazy Evaluation

Prev: Lazy Evaluation Next: Amortization and Persistence via Lazy Evaluation

5.2 Queues

Exercises

Exercise 5.1

This queue design can be extended to support the double-ended queue, or deque, abstraction, which allows reads and writes at both ends of the queue.

1. Implement this version of deques.
2. Prove that each operation takes $O(1)$ amortized time using the potential function $\Phi (f,r)=\mathrm{abs}(|f|-|r|)$, where abs is the absolute value function.

5.3 Binomial Heaps

Exercises

Exercise 5.2

Repeat the proof that insert runs in amortized $O(1)$ time using the banker’s method.

Exercise 5.3

Prove that the amortized costs of merge and deleteMin are still $O(\log n)$.

5.4 Splay Heaps

Exercises

Exercise 5.4

Implement smaller. Keep in mind that smaller should retain equal elements, but do not make a separate test for equality.

Exercise 5.5

Prove the zig-zag case.

Exercise 5.6

Prove that deleteMin also runs in $O(\log n)$ time.

Exercise 5.7

Write a sorting function that inserts elements into a splay tree and then performs an inorder traversal of the tree, dumping the elements into a list. Show that this function takes only $O(n)$ time on an already sorted list.

5.5 Pairing Heaps

Exercises

Exercise 5.8

Binary trees are often more convenient than multiway trees. Represent pairing heaps as half-ordered binary trees, where the element at each node is no greater than any element in its left subtree.

1. Write a function toBinary that converts pairing heaps from the existing representation into the type:

datatype BinTree = E' | T of Elem.T * BinTree * BinTree

2. Reimplement pairing heaps using this new representation.
3. Adapt the analysis of splay trees to prove that deleteMin and merge run in $O(\log n)$ amortized time for this new representation, and hence for the old representation as well. Use the same potential function as for splay trees.

5.6 The Bad News

Exercises

Exercise 5.9

Give examples of sequences of operations for which binomial heaps, splay heaps, and pairing heaps take much longer than indicated by their amortized bounds.

5.7 Chapter Notes