CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    Join Date
    Aug 2013
    Posts
    3

    [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!

  2. #2
    Join Date
    Aug 2013
    Posts
    55

    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?

  3. #3
    Join Date
    Aug 2013
    Posts
    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.

  4. #4
    Join Date
    Aug 2013
    Posts
    55

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

    Quote Originally Posted by Stratford View Post
    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.

  5. #5
    Join Date
    Aug 2013
    Posts
    3

    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
  •  





Click Here to Expand Forum to Full Width

Featured