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)
“Tattoo-shops, consulates, grim head-scarfed wives;
And out beyond its mortgaged half-built edges
Fast-shadowed wheat-fields, running high as hedges,
Isolate villages, where removed lives
Loneliness clarifies. Here silence stands
Like heat. Here leaves unnoticed thicken,
Hidden weeds flower....”
—Philip Larkin (1922–1986)
“Preschoolers think and talk in concrete, literal terms. When they hear a phrase such as “losing your temper,” they may wonder where the lost temper can be found. Other expressions they may hear in times of crisis—raising your voice, crying your eyes out, going to pieces, falling apart, picking on each other, you follow in your father’s footsteps—may be perplexing.”
—Ruth Formanek (20th century)