[Fibonacci Heaps] Promote a node after more than 2 loss children

Hello guys!

I have a question related to Fibonacci Heaps. In the decrease-key operation, if it is allowed lose s > 1 children before cut a node and meld it to the root list (promote the node), this alter the overall runtime complexity? I think there are no changes in the complexity due to the change of potencial will be the same. But I am not sure if I am right.

And how can this be proved by the amortized analysis?

I hope you can help me! :) Thanks in advance! :)

Implementations of standard data structures are so refined after years of evolution that you cannot hope to improve on them by changing details.

Why not just stick to the recipe and get the promised complexity?

I get this question as an exercise and I wanted to be sure about it.

Quote:

---

Originally Posted by Stratford

I get this question as an exercise and I wanted to be sure about it.

---

In your exercise, should the answer be based on the Fibonacci Heap in general or on a specific implementation you got handed out?

In general. It is related to the algorithm (of the operators) and their complexity.