Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al


The authors deal with a notion of marking the nodes of Fibonacci Heaps with the background that they are used to bound the amortized running time of the $ \text{Decrease-Key}$ or $ \text{Delete}$ algorithm, but not much intuition is given behind their use of it.

What things shall go bad if we do not use markings ? (or) use $ \text{Cacading-Cut}$ when the number of children lost from a node is not just $ 2$ but possibly more ?

The excerpt corresponding to this is as follows:

We use the mark fields to obtain the desired time bounds. They record a little piece of the history of each node. Suppose that the following events have happened to node $ x$ :

  1. at some time, $ x$ was a root,
  2. then $ x$ was linked to another node,
  3. then two children of $ x$ were removed by cuts.

As soon as the second child has been lost, we cut $ x$ from its parent, making it a new root. The field $ mark[x]$ is true if steps $ 1$ and $ 2$ have occurred and one child of $ x$ has been cut. The Cut procedure, therefore, clears $ mark[x]$ in line $ 4$ , since it performs step $ 1$ . (We can now see why line $ 3$ of $ \text{Fib-Heap-Link}$ clears $ mark[y]$ : node $ у$ is being linked to another node, and so step $ 2$ is being performed. The next time a child of $ у$ is cut, $ mark[y]$ will be set to $ \text{TRUE}$ .)


[The intuition of why to use the marking in the way stated in italics portion of the block above was made clear to me by the lucid answer here, but I still do not get the cost benefit which we get using markings what shall possibly go wrong if we do not use markings, the answer here talks about the benefit but no mathematics is used for the counter example given]


The entire corresponding portion of the text can be found here for quick reference.

Intuition behind the entire concept of Fibonacci Heap operations

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al


The potential function for the Fibonacci Heaps $ H$ is defined as follows:

$ $ \Phi(H)=t(H)+2m(H)$ $

where $ t(H)$ is the number of trees in the root list of the heap $ H$ and $ m(H)$ is the number of marked nodes in the heap.

Before diving into the Fibonacci Heap operations the authors try to convince us about the essence of Fibonacci Heaps as follows:

The key idea in the mergeable-heap operations on Fibonacci heaps is to delay work as long as possible. There is a performance trade-off among implementations of the various operations.($ \color{green}{\text{I do not get why}}$ ) If the number of trees in a Fibonacci heap is small, then during an $ \text{Extract-Min}$ operation we can quickly determine which of the remaining nodes becomes the new minimum node( $ \color{blue}{\text{why?}}$ ). However, as we saw with binomial heaps, we pay a price for ensuring that the number of trees is small: it can take up to $ \Omega (\lg n)$ time to insert a node into a binomial heap or to unite two binomial heaps. As we shall see, we do not attempt to consolidate trees in a Fibonacci heap when we insert a new node or unite two heaps. We save the consolidation for the $ \text{Extract-Min}$ operation, which is when we really need to find the new minimum node.


Now the problem which I am facing with the text is that they dive into proving the amortized cost mathematically using the potential method without going into the vivid intuition of the how or when the "credits" are stored as potential in the heap data structure and when it is actually used up. Moreover in most of the places what is used is "asymptotic" analysis instead of actual mathematical calculations, so it is not quite possible to conjecture whether the constant in $ O(1)$ for the amortized cost ( $ \widehat{c_i}$ ) is greater or less than the constant in $ O(1)$ for the actual cost ($ c_i$ ) for an operation.


$ $ \begin{array}{|c|c|c|} \hline \text{Sl no.}&\text{Operation}&\widehat{c_i}&c_i&\text{Method of cal. of $ \widehat{c_i}$ }&\text{Cal. Steps}&\text{Intuition}\ \hline 1&\text{Make-Fib-Heap}&O(1)&O(1)&\text{Asymptotic}&\Delta\Phi=0\text{ ; $ \widehat{c_i}=c_i=O(1)$ } &\text{None}\ \hline 2&\text{Fib-Heap-Insert}&O(1)&O(1)&\text{Asymptotic}&\Delta\Phi=1 \text{ ; $ \widehat{c_i}=c_i=O(1)+1=O(1)$ } &\text{None}\ \hline 3&\text{Fib-Heap-Min}&O(1)&O(1)&\text{Asymptotic}&\Delta\Phi=0;\text{ ; $ \widehat{c_i}=c_i=O(1)$ } &\text{None}\ \hline 4&\text{Fib-Heap-Union}&O(1)&O(1)&\text{Asymptotic}&\Delta\Phi=0;\text{ ; $ \widehat{c_i}=c_i=O(1)$ } &\text{None}\ \hline 5&\text{Fib-Extract-Min}&O(D(n))&O(D(n)+t(n))&\text{Asymptotic}&\Delta\Phi=D(n)-t(n)+1 &\text{$ \dagger$ }\ \hline 6&\text{Fib-Heap-Decrease-Key}&O(1)&O(c)&\text{Asymptotic}&\Delta\Phi=4-c &\text{$ \ddagger$ }\ \hline \end{array}$ $


$ \dagger$ – The cost of performing each link is paid for by the reduction in potential due to the link’s reducing the number of roots by one.

$ \ddagger$ – Why the potential function was defined to include a term that is twice the number of marked nodes. When a marked node $ у$ is cut by a cascading cut, its mark bit is cleared, so the potential is reduced by $ 2$ . One unit of potential pays for the cut and the clearing of the mark bit, and the other unit compensates for the unit increase in potential due to node $ у$ becoming a root.


Moreover the authors deal with a notion of marking the nodes of Fibonacci Heaps with the background that they are used to bound the amortized running time of the $ \text{Decrease-Key}$ or $ \text{Delete}$ algorithm, but not much intuition is given behind their use of it. What things shall go bad if we do not use markings or use $ \text{Cacading-Cut}$ when the number of children lost from a node is not just $ 2$ but possibly more. The excerpt corresponding to this is as follows:

We use the mark fields to obtain the desired time bounds. They record a little piece of the history of each node. Suppose that the following events have happened to node $ x$ :

  1. at some time, $ x$ was a root,
  2. then $ x$ was linked to another node,
  3. then two children of $ x$ were removed by cuts.

As soon as the second child has been lost, we cut $ x$ from its parent, making it a new root. The field $ mark[x]$ is true if steps $ 1$ and $ 2$ have occurred and one child of $ x$ has been cut. The Cut procedure, therefore, clears $ mark[x]$ in line $ 4$ , since it performs step $ 1$ . (We can now see why line $ 3$ of $ \text{Fib-Heap-Link}$ clears $ mark[y]$ : node $ у$ is being linked to another node, and so step $ 2$ is being performed. The next time a child of $ у$ is cut, $ mark[y]$ will be set to $ \text{TRUE}$ .)


Strictly I do not get the intuition behind the $ mark$ in the above block text especially the logic of doing the stuff in bold-italics.

[EDIT: The intuition of why to use the marking in the way stated was made clear to me by the lucid answer here, but I still do not get the cost benefit which we get using markings]


Note: It is quite a difficult question in the sense that it involves the description the problem which I am facing to understand the intuition behind the concept of Fibonacci Heap operations which is in fact related to an entire chapter in the CLRS text. If it demands too much in a single then please do tell me then I shall split it accordingly into parts. I have made my utmost attempt to make the question the clear. If at places the meaning is not clear, then please do tell me then I shall rectify it. The entire corresponding portion of the text can be found here. (Even the authors say that it is a difficult data structure, having only theoretical importance.)

Union-Find using Fibonacci Heaps

I am trying to do a MST algorithm implementation (Finding minimum spanning tree by extracting minimum edges and including every vertex) using Fibonacci Heaps. I want to minimize the time complexity by augmenting data structure if needed.

Approximate Algorithm :

MST(G) 2 T ← {} // set that will store the edges of the MST 3 for i ← 1..n 4 Vi ← {i} 5 Ei ← {(i, j) : j is a vertex and (i, j) is an edge of G} // set of all edges incident with vertex i 6 end for 7 while there is more than one set Vi 8 choose any Vi 9 extract minimum weight edge (u, v) from Ei 10 one of the endpoints u of this edge is in Vi. let Vj be the set that contains the other endpoint v 11 if i != j then 12 T ← T ∪ {(u, v)} 13 combine Vi and Vj into Vi (destroying Vj ) 14 combine Ei and Ej into Ei (destroying Ej ) 15 end if 16 end while 17 return T 18 end MST  

Time complexity Analysis Approach:

The for loop of line 3 − 5 requires O(V) MAKE-HEAP operations and a total of O(E) INSERT operations in line 5. Note that the size of each Ei set can be at most O(V) by definition. The total time is thus O(V + E) ~ O(E) (Because Fibonacci Heaps can support constant insertions for both MakeHeap and Insertions.

Now for Line 7-15 – We can at most extract O(E) edges in line 9 taking a total of (E lg V) time if after every insert we also consolidate. (Debatable) Can we use consolidate a bit more efficiently?

Also, I feel that we are doing a couple of Union operations further. How to optimize it in a way that I try to save maximum time by using some auxiliary data structures if possible.

Data structure implementation of MST (Minimum spanning tree) through Fibonacci heaps

How can a fibonacci heap store the information needed by the algorithm? In order to achieve good efficiency, when would you run the Consolidate routine?

Algorithm :

MST(G) 2 T ← {} // set that will store the edges of the MST 3 for i ← 1..n 4 Vi ← {i} 5 Ei ← {(i, j) : j is a vertex and (i, j) is an edge of G} // set of all edges incident with vertex i 6 end for 7 while there is more than one set Vi 8 choose any Vi 9 extract minimum weight edge (u, v) from Ei 10 one of the endpoints u of this edge is in Vi ; let Vj be the set that contains the other endpoint v 11 if i 6= j then 12 T ← T ∪ {(u, v)} 13 combine Vi and Vj into Vi (destroying Vj ) 14 combine Ei and Ej into Ei (destroying Ej ) 15 end if 16 end while 17 return T 18 end MST 

Would you have to add any additional fields to nodes in the heaps or use any additional data structures?

Order notation subtractions in Fibonacci Heap

Can order notation on its own imply:

$ O(D(n)) + O(t(H)) – t(H) = O(D(n))$

My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if c > 1.

Well, this is actually the case, but there are underlying factors. This equation appears in Fibonacci heap analysis in CLRS (518). The justification for this step comes from the underlying potential function. According to the authors, “we can scale up the units of potential to dominate the constant hidden in $ O(t(H))$ “. I want to know how this happens, but don’t really know how to ask this complicated question.

Modify Fibonacci Heap to Have a Linear Chain of Marked/Unmarked Nodes Only

In CLRS book there is an exercise (19.4-2) the aim of which is to create a linear chain of nodes by a sequence of Fibonacci-Heap operations. I have solved the problem by recursively making a union with a chain of two nodes, inserting a new minimum node and extracting the minimum, after which consolidation takes place and returns a new linear chain. Since there are no DECREASE-KEY or DELETE-NODE operations, no node is being marked.

My question is, is it possible to create a linear chain consisting of marked nodes only. If so, how?

I have tried several strategies. In one case I am getting a linear chain with all but the last node marked and I cannot proceed from there.

Another possibility is to get a chain as follows for $ n$ nodes:

Example of resulting FH

From here one can delete all the nodes on the shortest path for each sub-tree starting from the bottom to mark all of the nodes on the longer path. However, I cannot find a way to get this Fibonacci-Heap in the first place (and I am not sure whether it is possible). Any help would be appreciated.

Is there a reason to use specifically fibonacci sequence in planning poker?

I’ve noted that fibonacci sequence is quite popular in planning poker, but is it a reason for that particular sequence? Wouldn’t for example powers of 2 work equally well?

Both sequences are more or less exponential while fibonacci uses a factor of the golden ratio (approximately 1.6) so fibonacci has somewhat higher resolution and would allow to express more accurate estimates.

Is there for example any evidence that people tend to be able to estimate accurate enough to motivate the higher resolution? And if there is wouldn’t a even finer scale be motivated?

Fibonacci pagination

Today I stumbled upon this pagination concept and I found it fascinating: Fibonacci-based Pagination Concept.

It’s actually an old shot but it made me think as I’ll need to paginate some content in the near future.

Pages will soon become hundred and eventually thousands, so I’ll need some “clever” pagination [in groups] (10-30 | 31-32-33…37-38-39 | 40-70) instead of just listing pages from 1 to 200.

As mentioned before, I find this approach fascinating but I also feel that the user needs to be able to reach the page that he wants to with the least possible number of steps.

I’m not a UX expert so you’ll be the judge: would you consider this a good or a bad approach? And what use case is this a good or a bad approach for?

MY USE CASE

I’m unaware of the creator’s use case. I’m showing a content that is ordered by time but the time variable is irrelevant to the user. Pages are there just to fragment content.

User by itself doesn’t need to go to a specific page as items have a permalink.

Say that I have posts which contain aphorisms: they have been posted in different times so I can list them and order them and eventually split them into pages, but the date/time itself is irrelevant.

Python program for fibonacci sequence using a recursive function

A Fibonacci sequence is the integer sequence of 0, 1, 1, 2, 3, 5, 8.....

The first two terms are 0 and 1. All other terms are obtained by adding the preceding two terms.

def recur_fibonacci(n):    if n <= 1:        return n    else:        return(recur_fibonacci(n-1) + recur_fibonacci(n-2))  nterms = int(input("How many terms? "))  if nterms <= 0:    print("Please enter a positive integer!") else:    print("Fibonacci sequence:")    for i in range(nterms):        print(recur_fibonacci(i)) 

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.