[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! :)
Re: [Fibonacci Heaps] Promote a node after more than 2 loss children
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?
Re: [Fibonacci Heaps] Promote a node after more than 2 loss children
I get this question as an exercise and I wanted to be sure about it.
Re: [Fibonacci Heaps] Promote a node after more than 2 loss children
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?
Re: [Fibonacci Heaps] Promote a node after more than 2 loss children
In general. It is related to the algorithm (of the operators) and their complexity.