The step of delete-min that ensures that there is at most one tournament tree of each possible height is called consolidation.
computer science
Description
Problem 1 Quake Heaps:
The step of delete-min that ensures that there is at most one tournament tree of
each possible height is called consolidation. In this problem, you are asked to think
about different variants of the consolidation step.
(a) Suppose that we omit the consolidate step in delete-min. What happens to the running time?
(b) Suppose that after the quake step in delete-min, we repeat the consolidate step. Show that this does not change the asymptotic running times.
(c) (voluntary, 5 extra credits) What happens if we perform the consolidate step
at the end of insert instead of delete-min?
Problem 2 Quake Heaps: Analysis II 10 credits
Please look at the notes about quake heaps on the website. Suppose we change the constant in Invariant 1 from 3/4 to 2/3. How does the analysis need to change? In particular, what happens to the proof of Lemma 7?
Note: The numbers refer to the numbering in the write-up
Problem 3 Potential Functions
In class, we have analyzed quake heaps with the accounting method. An alternative method is the potential method. We consider a data structure D. Let D be the set of all possible states of D. A potential function Φ : D → N0 is a function that assigns a natural number Φ(D) to every state D ∈ D of the data structure. For the original state D0, we require that Φ(D0) = 0.
We define the amortized cost of an operation X on the data structure. Let D
be the data structure before the operation X, and D0
the data structure after X.
Let cX be the actual cost of X. Then, the amortized cost of X, ˆcX, is defined as
cˆX := cX + Φ(D0
) − Φ(D).
