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)
“Even in harmonious families there is this double life: the group life, which is the one we can observe in our neighbour’s household, and, underneath, another—secret and passionate and intense—which is the real life that stamps the faces and gives character to the voices of our friends. Always in his mind each member of these social units is escaping, running away, trying to break the net which circumstances and his own affections have woven about him.”
—Willa Cather (1873–1947)
“Love is a great thing. It is not by chance that in all times and practically among all cultured peoples love in the general sense and the love of a man for his wife are both called love. If love is often cruel or destructive, the reasons lie not in love itself, but in the inequality between people.”
—Anton Pavlovich Chekhov (1860–1904)