Why do Fibonacci heaps need cascading cuts?

Question

I'm learning f-heap from 'introduction to algorithms', and the 'decrease-key' operation really confuses me -- why does this need a 'cascading-cut' ?

if this operation is removed:

1. the cost of make-heap(), insert(), minimum() and union() remains obviously unchanged
2. extract-min() is still O(D(n)), because in the O(n(H)) 'consolidate' operation, the cost of most rooted trees can be payed when they were added to the root list, and the remaining costs O(D(n))
3. decrease-key(): obviously O(1)

As for D(n), though i can't explain it precisely, i think it is still O(lgn), cuz without 'cascading-cut', a node may just be moved to root list a bit later, and any node hides under its father does not affect the efficiency. At least, this will not make the situation worse.

apologize for my poor english :(

anyone can help? thanks

Answer 1

The reason for the cascading cut is to keep D(n) low. It turns out that if you allow any number of nodes to be cut from a tree, then D(n) can grow to be linear, which makes delete and delete-min take linear time.

Intuitively, you want the number of nodes in a tree of order k to be exponential in k. That way, you can have only logarithmically many trees in a consolidated heap. If you can cut an arbitrary number of nodes from a tree, you lose this guarantee. Specifically, you could take a tree of order k, then cut all of its grandchildren. This leaves a tree with k children, each of which are leaves. Consequently, you can create trees of order k with just k + 1 total nodes in them. This means that in the worst case you would need a tree of order n - 1 to hold all the nodes, so D(n) becomes n - 1 rather than O(log n).

Hope this helps!