-
August 16th, 2013, 05:41 PM
#1
[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!
-
August 19th, 2013, 04:05 PM
#2
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?
-
August 19th, 2013, 04:19 PM
#3
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.
-
August 19th, 2013, 06:12 PM
#4
Re: [Fibonacci Heaps] Promote a node after more than 2 loss children
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?
Last edited by zizz; August 19th, 2013 at 06:38 PM.
-
August 20th, 2013, 12:20 AM
#5
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.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|