CareerCup

Delete using postorder traversal... i dont see anything special in this

In postorder traversal you can go all the way down the tree which can bee n length, that mean it would take o(n) !?

I thougth on this particular problem for about 3 days. There are no solutions for it in the internet.

In short, we need to maintain all the leafs in a doubly-linked list. It can be done not affecting the amortized asymptotic time of other fibonacci-heap operations.
Then we just consequentially delete r elements from this list of leafs, marking the parents the same way we mark them in the procedure 'decrease-key'.
Thus, amortized running time of an operation FIB-HEAP-PRUNE(H, r) is just O(n[H]).

I can't think of a more efficient algorithm not affecting asymptotic running time of other fib-heap operations.

I am studying this question. The problem with your solution is that if we remove a leaf and then try the next one, if its the child of the same parent we need to do a cascading cut which will result in O(rlogn). I though of keeping a link list of size n, which each element i keeps a list of pointers to all nodes with subtree size of i. Then the problem would be to find a combination of numbers that add up to r. Which I don't know how. It will be the sum_subset problem which is np-complete.

I mean O(r), of course.