Talk:Fibonacci heap

Mergeable priority queue ADT

Has anyone else ever heard it mentioned that Fibonacci heaps can be used to efficiently implement mergeable priority queues? If you're familiar with CS then you can see from the definitions that it's clearly true (and that merging is far more efficient than if a traditional heap had been used for the priority queues) though I have yet to find an application where merging priority queues needs to be done frequently enough to make it useful :) Anyway, I'd like some opinions on adding that tidbit to the article. DaveWF 07:48, 14 February 2007 (UTC)

Why "Fibonacci"

Although the article mentions that Fibonacci numbers "are used" in the running time analysis, and that Fibonacci numbers give a constraint for subtree size given the order of a node, the "why" of this is not described. I will look into it and add an explanation if I can, but if I don't, someone else could. --CyHawk (talk) 08:42, 15 August 2008 (UTC)

I think the analysis relies on the fact that the number of ancestors of any node is exponential in its degree, n. This is proven by showing that the number of ancestors grows faster than the Fibonacci numbers $F_{n}$ do, since $F_{n}$ ~ $\varphi ^{n}/{\sqrt {5}}$. In particular, you can show that $\sum _{i=0}^{n}A(i)\leq A(n+2)-1$, and so since $\sum _{i=0}^{n}F_{i}=F_{n+2}-1$, $A(1)=F_{1}$, and $A(2)>F_{2}$, $A(n)\geq F_{n}$. A(i) denotes the number of ancestors of a node of degree i. Something like that. WuTheFWasThat (talk) 17:28, 13 September 2009 (UTC)

Summary of running times

The linked list deletemin and delete operations assumes a search is required. If one is given a pointer to the item that must be deleted, then deletion can be done in Theta(1) worst-case time. (in fact, all the running times should be made more precise - I would list them as Theta with an explanation that this is worst-case running time). —Preceding unsigned comment added by Trachten (talk • contribs) 15:14, 7 October 2009 (UTC)

This list seems to be a little inconsistent. Are accessmin and deletemin really possible in O(1) for binary trees? Also, a statement for linked lists appears to be confusing as it depends on what case (insertion or removal) is preferred by an implementation.--85.178.10.62 (talk) 20:01, 31 August 2008 (UTC)

I think it is misleading that this table states that the insert operation is O(log(n)) on a binary heap, and doesn't mention anything about average time. After each of the log(n) swaps that *could possibly* occur during insertion into a binary heap, the likelihood that the swapping must continue decreases (on average by a factor of about 2). Thus, insertion into a binary heap averages about O(1). (1/2 + 1/4 + 1/8 + ... = 1.) --128.187.80.2 (talk) 18:26, 30 July 2009 (UTC)

What about adding sorted linked list and/or sorted (dynamic) array to this summary? -- akerbos 17:55 Oct 23 2010