$3$ Frequent Consolidation

In Fibonacci Heaps, the consolidate procedure is called only during ExtractMin$().$ That makes the data structure rather "messy". In this problem, we explore some ways that might make Fibonacci Heaps tidier. Throughout, we will keep the same invariant as before: $$1$ credit on each root in the root list and $$2$ on each marked node.

Recall that in the standard implementation of Fibonacci Heaps, when we insert an item $x,$ we just make $x$ its own heap $($with a single item$)$ and add that heap to the root list.

Suppose that we modify the Insert operation and have it call the consolidate procedure after each new item is added to the root list. Explain why we cannot maintain the invariant and still have Insert run in $(1)$ amortized time.

The astute observer would correctly claim that the previous question is silly because if we consolidate after every insertion, then the roots in the root list would always have unique degree. If we keep the roots sorted by degree in the root list $($starting with degree $0),$ then we can easily combine the newly inserted $x$ with the heaps already in the root list. The process will be very similar to the ripple$-$carry adder in the binary counter example for amortized analysis.

For example, if the root list has roots with degree $0,1,2,4$ and $7,$ then we fist merge the new heap $($which has degree $0)$ with the degree $0$ root. This makes a root with degree $1,$ which we merge with the existing root with degree $1.$ That makes a root with degree $2$ which gets merged and forms a root with degree $3.$ After that we stop merging and the resulting root list has roots with degree $3,4$ and $7.$ We can just use the $$1$ stored at each root to pay for the merges, add $$1$ to the new root and Insert would still run in $(1)$ amortized time.

Explain what happens to the amortized running times of Extract$-$Min, Decrease$-$Key and Merge operations under such a scheme.

Another variation of the previous scheme is to keep an array Root $[]$ indexed by degree so that Root $[$i$]$ points to the unique heap where the root has degree $i($if one exists$).$ That is$,$ we keep an array of roots instead of a list of roots. Does the binary counter scheme still work to keep Insertion at $(1)$ amortized running time? Explain.

Explain what happens to the amortized running times of Extract$-$Min, Decrease$-$Key and Merge operations under our new scheme.