Fibonacci heaps are efficient in an amortized sense, but how efficient are they in the worst case? Specifically, what is the worst-case time complexity of each of these operations on an n-node Fibonacci heap?
On
I almost agree with the great answer from @templatetypedef.
There cannot be a tree of a classical Fibonacci heap with $n$ marked nodes. This would mean that the height of the tree is O(n), but since for each subtree of rank $k$ its children are of ranks $\geq 0, \geq 1, ... , \geq k-1$. It is easy to see that the depth of the tree is at most O(logn). And therefore a single Decrease-key operation can cost O(logn).
I checked this thread, and it takes some modification of the Fibonacci heap, as it has marked node in the root list and does operation which do not belong to the Fibonacci heap.
The find-min operation on a Fibonacci heap always takes worst-case O(1) time. There's always a pointer maintained that directly points to that object.
The cost of a delete-min, in the worst-case, takes time Θ(n). To see this, imagine starting with an empty heap and doing a series of n insertions into it. Each node will be stored in its own tree, and doing a delete-min the heap will coalesce all these objects into O(log n) trees, requiring Θ(n) work to visit all the nodes at least once.
The cost of an insertion is worst-case O(1); this is just creating a single node and adding it to the list. A merge is similarly O(1) since it just splices two lists together.
The cost of a decrease-key in the worst case is Θ(n). It's possible to build a degenerate Fibonacci heap in which all the elements are stored in a single tree consisting of a linked list of n marked nodes. Doing a decrease-key on the bottommost node then triggers a run of cascading cuts that will convert the tree into n independent nodes.