Number of trees in a Fibonacci Heap without CASCADING-CUT

In summary: I'm not sure why.Can you please clarify?The sum was supposed to represent the minimal amount of nodes in all trees.Yes, the sum represents the minimal amount of nodes in all trees, so summing over all values of k yields an equation for the minimum number of nodes in a tree of depth k:\sum_{k=1}^{T} k = \frac{T(T+1)}{2} = n.
  • #1
CGandC
326
34
Homework Statement
The question relates to Fibonacci heaps. Suppose DECRASE-KEY was implemented without CASCADING-CUT.
Prove that after CONSOLIDATE operation on the Fibonacci heap, the amount of trees in the heap is at most ## O( \sqrt{n} ) ##.
Relevant Equations
( The question is in the context of the section about Fibonacci heaps from 2nd edition of CLRS )
--- ##n## refers to the amount of nodes in the Fibonacci heap.
--- order of a tree in heaps is defined as the number of children of a root.
--- In a different exercise I showed that the minimal amount of nodes in a tree ( from Fibonacci heap in which DECREASE-KEY is implemented without CASCADING-CUT ) of order ##k## is ##k+1##.
I know that the maximum number of trees in a heap will be when all the trees are of smallest order as possible. Then, after performing CONSOLIDATE operation on the heap, all the newly created trees in the heap will be of different orders. Since in a different exercise I showed that the minimal amount of nodes in a tree ( from Fibonacci heap in which DECREASE-KEY is implemented without CASCADING-CUT ) of order ##k## is ##k+1##, thus, we can sum the nodes from all the minimal trees, bound them by ##n## and get an upper-bound of ## O( \sqrt{n} ) ## for the number of trees.

The above attempt is not necessarily correct and has logical gaps. My main trouble is that the sum ## \sum_{k=1}^{k=n} k+1 ## will give me an upper bound of ##O(n^2)## and not of ##O(\sqrt{n})##. In any-case I'm stuck and I'd really appreciate help, I have no idea how to proceed and I feel like I've been brooding for too-long on this problem.
 
Physics news on Phys.org
  • #2
CGandC said:
My main trouble is that the sum ## \sum_{k=1}^{k=n} k+1 ## will give me an upper bound of ##O(n^2)## and not of ##O(\sqrt{n})##.
That is not a problem. It may help if you use ## N ## to represent the total number of nodes and ## T ## the total number of trees. What limit are you summing to with this notation? What does the sum represent?
 
  • #3
The sum was supposed to represent the minimal amount of nodes in all trees. Suppose this sum was ## S ##, after the CONSOLIDATE operation, I'd have at most ##O( log(n) )## trees in the Fibonacci heap.
Now, I think If I were to get an upper-bound of ## O(\sqrt{n}) ## on the number of trees, I'd need to have about ## 2^\sqrt{n} ## nodes, because only in such case I'd have ##T = log(2^\sqrt{n}) = \sqrt{n} ## trees, so I think the answers lies in this. But on the other hand, the analysis I did does not relate to the sum ## S ##, so I am perplexed right now..
 
  • #4
Please write the sum again as ## \sum_{k=1}^X k+1 ## (which we know is ## \frac{X^2 + 3X}2 ##). Now write ## Y = \sum_{k=1}^X k+1 = \frac{X^2 + 3X}2 ##. What do you think ## X \text{ and } Y ## are here? What is it that is equal to ## k + 1 ## for each something that has something equal to ## k ##?
 
Last edited:
  • #5
CGandC said:
The sum was supposed to represent the minimal amount of nodes in all trees. Suppose this sum was ## S ##, after the CONSOLIDATE operation, I'd have at most ##O( log(n) )## trees in the Fibonacci heap.
No you wouldn't, you are about to prove that you would have at most ##O( \sqrt n )## trees.
 
  • #6
Actually let's start this from scratch: write down an expression for the minimum number of nodes in a tree of depth ## k ##.
 
  • #7
For the trees in the Fibonacci heap, the minimum number of nodes in a tree of order ## k ## is ## k + 1 ##. How do I proceed to use this fact together with the fact that after performing CONSOLIDATE operation on all the trees, each tree created in the new heap will be of different order?
 
  • #8
If you have ## T_0 ## trees what is the minimum number of nodes they will cover? What will be the order of these trees? If after consolidation you have the maximum number of trees left, and this number is ## T ## write down a list of the orders of the trees.
 
  • #9
(actually you were nearly there a few posts ago, I'll try from there)

CGandC said:
The sum was supposed to represent the minimal amount of nodes in all trees.
Exactly. So write down an expression for the minimal number ## N ## of nodes in ## T ## trees (after consolidation).
 
Last edited:
  • #10
Like this?:

Let ## Tree_1, ... ,Tree_T ## denote the trees after consolidating.
## Tree_1 ## will have at-least 1 node ( ## Tree_1 ## must be of at-least order ##0## )
## Tree_2 ## will have at-least 2 node ( ## Tree_2 ## must be of at-least order ##1## )
.
.
.
## Tree_T ## will have at-least T nodes ( ## Tree_T ## must be of at-least order ##T-1## )

the number of their nodes will satisfy ## \sum_{k=1}^{T} k \leq n \longrightarrow \frac{T^2}{2} \leq \sum_{k=1}^{T} k = \frac{T(T+1)}{2} \leq n \longrightarrow T^2 \leq 2n \longrightarrow T \leq \sqrt{2}\sqrt{n} ##

Edit:
It should be ## \sum_{k=1}^{T} k = \frac{T(T+1)}{2} = n ## and from here ## \frac{T^2}{2} \leq n ##
 
  • Like
Likes pbuk
  • #11
CGandC said:
It should be ## \sum_{k=1}^{T} k = \frac{T(T+1)}{2} = n ## and from here ## \frac{T^2}{2} \leq n ##
Well it's actually ## \frac{T^2 + T}{2} \leq n ## but as we are only interested in big-O let's write (with a bit of short-circuiting) ## T^2 = \mathcal O (N) ##.

So from this, ## T = \mathcal O(?) ##
 
  • Like
Likes CGandC
  • #12
## \mathcal O(T) = O(\sqrt{N}) ## !
Thanks alot! I was vacillating on this problem for lots of hours, but I feel like I learned a lot about fibonacci heaps.
 
  • Like
Likes pbuk

Related to Number of trees in a Fibonacci Heap without CASCADING-CUT

1. How is the number of trees in a Fibonacci Heap without CASCADING-CUT calculated?

The number of trees in a Fibonacci Heap without CASCADING-CUT is calculated by counting the number of nodes with the same degree (number of child nodes) in the heap. Each unique degree represents a separate tree in the heap.

2. What is the significance of the number of trees in a Fibonacci Heap without CASCADING-CUT?

The number of trees in a Fibonacci Heap without CASCADING-CUT represents the efficiency of the heap. A smaller number of trees indicates a more efficient heap, as it requires less operations to maintain the heap's structure.

3. How does the number of trees in a Fibonacci Heap without CASCADING-CUT affect the time complexity of operations?

The number of trees in a Fibonacci Heap without CASCADING-CUT directly affects the time complexity of operations. A smaller number of trees results in faster operations, as there are fewer trees to traverse and maintain during operations.

4. Can the number of trees in a Fibonacci Heap without CASCADING-CUT change during operations?

Yes, the number of trees in a Fibonacci Heap without CASCADING-CUT can change during operations. Insertion and union operations can increase the number of trees, while delete and extract-min operations can decrease the number of trees.

5. What is the maximum number of trees in a Fibonacci Heap without CASCADING-CUT?

The maximum number of trees in a Fibonacci Heap without CASCADING-CUT is n, where n is the number of nodes in the heap. This occurs when each node in the heap has a unique degree, resulting in n separate trees.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Replies
3
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
9
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Replies
4
Views
668
Back
Top