Fibonacci Heap - Summary of Running Times

Summary of Running Times

Common Operations Effect Unsorted Linked List Self-balancing binary search tree Binary heap Binomial heap Fibonacci heap Brodal queue Pairing heap
insert(data,key) Adds data to the queue, tagged with key O(1) O(log n) O(log n) O(log n) O(1) O(1) O(1)
findMin -> key,data Returns key,data corresponding to min-value key O(n) O(log n) or O(1) (**) O(1) O(log n) O(1) O(1) O(1)
deleteMin Deletes data corresponding to min-value key O(n) O(log n) O(log n) O(log n) O(log n)* O(log n) O(log n)*
delete(node) Deletes data corresponding to given key, given a pointer to the node being deleted O(1) O(log n) O(log n) O(log n) O(log n)* O(log n) O(log n)*
decreaseKey(node) Decreases the key of a node, given a pointer to the node being modified O(1) O(log n) O(log n) O(log n) O(1)* O(1) Unknown but bounded: *
merge(heap1,heap2) -> heap3 Merges two heaps into a third O(1) O(m log(n+m)) O(m + n) O(log n)*** O(1) O(1) O(1)

(*)Amortized time
(**)With trivial modification to store an additional pointer to the minimum element
(***)Where n is the size of the larger heap

Read more about this topic:  Fibonacci Heap

Famous quotes containing the words summary, running and/or times:

    I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.
    George Gordon Noel Byron (1788–1824)

    But the ball is lost and the mallet slipped long since from the hands
    Under the running tap that are not the hands of a child.
    Louis MacNeice (1907–1963)

    But this I know; the writer who possesses the creative gift owns something of which he is not always master—something that at times strangely wills and works for itself.... If the result be attractive, the World will praise you, who little deserve praise; if it be repulsive, the same World will blame you, who almost as little deserve blame.
    Charlotte Brontë (1816–1855)