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:
“Product of a myriad various minds and contending tongues, compact of obscure and minute association, a language has its own abundant and often recondite laws, in the habitual and summary recognition of which scholarship consists.”
—Walter Pater (1839–1894)
“These six things doth the Lord hate: yea, seven are an abomination unto him: A proud look, a lying tongue, and hands that shed innocent blood, an heart that deviseth wicked imaginations, feet that be swift in running to mischief, a false witness that speaketh lies, and he that soweth discord among brethren.”
—Bible: Hebrew Proverbs 6:16-19.
“These have been wonderful years. How many happy, happy times we have traveled about together! Day and night, in stage coaches, on freight trains, over the mountains and across the prairies, hungry and tired, we have wandered. The work was sometimes hard and discouraging but those were happy and useful years.”
—Susan B. Anthony (1820–1906)