11.2 Suppose a binomial queue of N = 2k − 1 elements is built. Alternately perform M insert and deleteMin pairs. Clearly, each operation takes O(logN) time. Why does this not contradict the amortized bound of O(1) for insertion? - Get solution
11.3 Show that the amortized bound of O(logN) 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. - Get solution
11.4 Show how to merge two skew heaps with one top-down pass and reduce the merge cost to O(1) amortized time. - Get solution
11.5 Extend skew heaps to support the decreaseKey operation in O(logN) amortized time. - Get solution
11.6 Implement Fibonacci heaps and compare their performance with that of binary heaps when used in Dijkstra’s algorithm. - Get solution
11.7 A standard implementation of Fibonacci heaps requires four links per node (parent, child, and two siblings). Show how to reduce the number of links, at the cost of at most a constant factor in the running time. - Get solution
11.8 Show that the amortized time of a zig-zig splay is at most 3(Rf (X) − Ri(X)). - Get solution
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) logN).
b. If qi is the number of times that item i is accessed, and qi > 0 for all i, then the
total access time is
b. Improve the bound to O(N logN). - Get solution
11.11 In Chapter 5, we described rehashing: 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). - Get solution
11.12 What is the maximum depth of a Fibonacci heap? - Get solution
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): Insert item x on the front end of the deque.
pop(): Remove the front item from the deque and return it.
inject(x): Insert item x on the rear end of the deque.
eject(): Remove the rear item from the deque and return it.
findMin(): Return the smallest item from the deque (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. - Get solution
11.14 Show that the binomial queues actually support merging in O(1) amortized time. Define the potential of a binomial queue to be the number of trees plus the rank of the largest tree. - Get solution
11.15 Suppose that in an attempt to save time, we splay on every second tree operation.
Does the amortized cost remain logarithmic? - Get solution
11.16 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. - Get solution
11.17 As a result of a splay, most of the nodes on the access path are moved halfway towards the root, while a couple of nodes on the path move down one level. This suggests using the sum over all nodes of the logarithm of each node’s depth as a potential function.
a. What is the maximum value of the potential function?
b. What is the minimum value of the potential function?
c. The difference in the answers to parts (a) and (b) gives some indication that this potential function isn’t too good. Show that a splaying operation could increase the potential by (N/ logN). - Get solution
