Question? Leave a message!




FIBONACCI HEAPS

FIBONACCI HEAPS
FIBONACCI HEAPS preliminaries ‣ insert ‣ extract the minimum ‣ decrease key ‣ bounding the rank ‣ meld and delete ‣ Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on Sep 8, 2013 7:00 AMPriority queues performance cost summary operation linked list binary heap binomial heap Fibonacci heap † MAKEHEAP O(1) O(1) O(1) O(1) ISEMPTY O(1) O(1) O(1) O(1) INSERT O(1) O(log n) O(log n) O(1) EXTRACTMIN O(n) O(log n) O(log n) O(log n) DECREASEKEY O(1) O(log n) O(log n) O(1) DELETE O(1) O(log n) O(log n) O(log n) MELD O(1) O(n) O(log n) O(1) FINDMIN O(n) O(1) O(log n) O(1) † amortized Ahead. O(1) INSERT and DECREASEKEY, O(log n) EXTRACTMIN. 2Fibonacci heaps Theorem. FredmanTarjan 1986 Starting from an empty Fibonacci heap, any sequence of m INSERT, EXTRACTMIN, and DECREASEKEY operations involving n INSERT operations takes O(m + n log n) time. this statement is a bit weaker than the actual theorem Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms MICHAEL L. FREDMAN University of California, San Diego, L.a Jolla, California AND ROBERT ENDRE TARJAN ATT Bell Laboratories, Murray HilI, New Jersey Abstract. In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated Fheaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. Fheaps support arbitrary deletion from an nitem heap in qlogn) amortized time and all other standard heap operations in o( 1) amortized time. Using Fheaps we are able to obtain improved running times for several network optimization algorithms. In particular, we obtain the following worstcase bounds, where n is the number of vertices and m the number of edges in the problem graph: ( 1) O(n log n + m) for the singlesource shortest path problem with nonnegative edge lengths, improved from O(m logfmh+2)n); (2) O(nlog n + nm) for the allpairs shortest path problem, improved from O(nm lo,,,+2,n); (3) O(nlogn + nm) for the assignment problem (weighted bipartite matching), improved from O(nm log0dn+2)n); (4) O(mj3(m, n)) for the minimum spanning tree problem, improved from O(mloglo,,.+2,n), where j3(m, n) = min i 1 log 5 m/n). Note that B(m, n) 5 logn if m 2 n. Of these results, the improved bound for minimum spanning trees is the most striking, although all the results give asymptotic improvements for graphs of appropriate densities. Categories and Subject Descriptors: E.l Data: Data Structurestrees; graphs; F.2.2 Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms and Problemscomputations on 3 discrete structures; sorting and searching; G.2.2 Discrete Mathematics: Graph Theorygraph algo rithms; network problems; trees General Terms: Algorithms, Theory Additional Key Words and Phrases: Heap, matching, minimum spanning tree, priority queue, shortest Pati ’ A preliminary version of this paper appeared in the Proceedings of the 25th IEEE Symposium on the Foundations of Computer Science (Singer Island, Fla., Oct. 2426). IEEE, New York, 1984, pp. 338 346, 0 IEEE. Any portion of this paper that appeared in the preliminary version is reprinted with permission. This research was supported in part by the National Science Foundation under grant MCS 820403 1. Authors’ addresses: M. L. Fredman, Electrical Engineering and Computer Science Department, Uni versity of California, San Diego, La Jolla, CA 92093; R. E. Tarjan, ATT Bell Laboratories, Murray Hill, NJ 07974. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1987 ACM 0004541 l/87/07000596 1.50 Journal ofthe Association for Computing Machinery, Vol. 34, No. 3, July 1987, Pages 596615. Fibonacci heaps Theorem. FredmanTarjan 1986 Starting from an empty Fibonacci heap, any sequence of m INSERT, EXTRACTMIN, and DECREASEKEY operations involving n INSERT operations takes O(m + n log n) time. History. Ingenious data structure and application of amortized analysis. Original motivation: improve Dijkstra's shortest path algorithm from O(m log n) to O(m + n log n). Also improved bestknown bounds for allpairs shortest paths, assignment problem, minimum spanning trees. 4FIBONACCI HEAPS structure ‣ insert ‣ extract the minimum ‣ decrease key ‣ bounding the rank ‣ meld and delete ‣ SECTION 19.1Fibonacci heaps Basic idea. Similar to binomial heaps, but less rigid structure. Binomial heap: eagerly consolidate trees after each INSERT; implement DECREASEKEY by repeatedly exchanging node with its parent. Fibonacci heap: lazily defer consolidation until next EXTRACTMIN; implement DECREASEKEY by cutting off node and splicing into root list. Remark. Height of Fibonacci heap is Θ(n) in worst case, but it doesn't use sink or swim operations. 6Fibonacci heap: structure Set of heapordered trees. each child no smaller than its parent heapordered tree 17 24 23 7 3 root 30 26 46 18 52 41 heap H 35 44 39 7Fibonacci heap: structure Set of heapordered trees. Set of marked nodes. used to keep trees bushy (stay tuned) min 17 24 23 7 3 30 26 26 46 18 18 52 41 marked heap H 35 44 39 39 8Fibonacci heap: structure Heap representation. Store a pointer to the minimum node. Maintain tree roots in a circular, doublylinked list. min 17 24 23 7 3 30 26 26 46 18 18 52 41 heap H 35 44 39 39 9Fibonacci heap: representation Node representation. Each node stores: A pointer to its parent. A pointer to any of its children. A pointer to its left and right siblings. Its rank = number of children. Whether it is marked. min rank = 3 17 24 23 7 3 30 26 26 46 18 18 52 41 children are in a heap H 35 circular doublylinked list 44 39 39 10Fibonacci heap: representation Operations we can do in constant time: Determine rank of a node. Find the minimum element. Merge two root lists together. Add or remove a node from the root list. Remove a subtree and merge into root list. Link the root of a one tree to root of another tree. min rank = 3 17 24 23 7 3 30 26 26 46 18 18 52 41 heap H 35 44 39 39 11Fibonacci heap: notation notation meaning number of nodes n rank(x) number of children of node x rank(H) max rank of any node in heap H trees(H) number of trees in heap H marks(H) number of marked nodes in heap H rank(H) = 3 trees(H) = 5 marks(H) = 3 n = 14 min rank = 1 rank = 3 17 24 23 7 3 30 26 26 46 18 18 52 41 heap H 35 44 39 39 12Fibonacci heap: potential function Potential function. Φ(H)  = trees(H) + 2 ⋅ marks(H) trees(H) = 5 marks(H) = 3 Φ(H) = 5 + 2⋅3 = 11 min 17 24 23 7 3 30 26 26 46 18 18 52 41 heap H 35 44 39 39 13FIBONACCI HEAPS preliminaries ‣ insert ‣ extract the minimum ‣ decrease key ‣ bounding the rank ‣ meld and delete ‣ SECTION 19.2Fibonacci heap: insert Create a new singleton tree. Add to root list; update min pointer (if necessary). insert 21 21 min 17 24 23 7 3 30 26 26 46 18 18 52 41 heap H 35 44 39 39 15Fibonacci heap: insert Create a new singleton tree. Add to root list; update min pointer (if necessary). insert 21 min 17 24 23 7 21 3 30 26 26 46 18 18 52 41 heap H 35 44 39 39 16Fibonacci heap: insert analysis Actual cost. c = O(1). i one more tree; Change in potential. ∆Φ = Φ(H ) – Φ(H ) = +1. i i–1 no change in marks Amortized cost. ĉ = c + ∆Φ = O(1). i i Φ(H)  = trees(H) + 2 ⋅ marks(H) min 17 24 23 7 21 3 30 26 26 46 18 18 52 41 heap H 35 44 39 39 17FIBONACCI HEAPS preliminaries ‣ insert ‣ extract the minimum ‣ decrease key ‣ bounding the rank ‣ meld and delete ‣ SECTION 19.2Linking operation Useful primitive. Combine two trees T and T of rank k. 1 2 Make larger root be a child of smaller root. Resulting tree T ' has rank k + 1. tree T tree T tree T' 1 2 3 3 15 15 18 52 41 18 52 41 56 24 33 39 44 39 44 77 56 24 33 77 still heapordered 19Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. min 7 24 23 17 3 30 26 26 26 46 18 52 41 35 39 44 20Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. min 7 24 23 17 18 52 41 39 44 30 26 26 26 46 35 21Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. current min 7 24 23 17 18 52 41 39 44 30 26 26 26 46 35 22Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 24 23 17 18 52 41 39 44 30 26 26 26 46 35 23Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 24 23 17 18 52 41 39 44 30 26 26 26 46 35 24Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 24 23 17 18 52 41 39 44 30 26 26 26 46 35 25Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank link 23 to 17 0 1 2 3 current min 7 24 23 17 18 52 41 39 44 30 26 26 26 46 35 26Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank link 17 to 7 0 1 2 3 current min 7 24 17 18 52 41 23 39 44 30 26 26 26 46 35 27Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank link 24 to 7 0 1 2 3 current min 24 7 18 52 41 17 30 39 44 26 26 26 46 35 23 28Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 18 52 41 24 17 30 39 44 26 26 26 46 23 35 29Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 18 52 41 24 17 30 39 44 26 26 26 46 23 35 30Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 18 52 41 24 17 30 39 44 26 26 26 46 23 35 31Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank link 41 to 18 0 1 2 3 current min 7 18 52 41 24 17 30 39 44 26 26 26 46 23 35 32Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 52 18 24 17 30 41 39 26 26 26 46 23 44 35 33Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. rank 0 1 2 3 current min 7 52 18 24 17 30 41 39 26 26 26 46 23 44 35 34Fibonacci heap: extract the minimum Delete min; meld its children into root list; update min. Consolidate trees so that no two roots have same rank. stop (no two trees have same rank) min 7 52 18 24 17 30 41 39 26 26 26 46 23 44 35 35Fibonacci heap: extract the minimum analysis Actual cost. c = O(rank(H)) + O(trees(H)). i ≤ rank(H) children O(rank(H)) to meld min's children into root list. ≤ rank(H) + trees(H) – 1 root nodes O(rank(H)) + O(trees(H)) to update min. O(rank(H)) + O(trees(H)) to consolidate trees. number of roots decreases by 1 after each linking operation Change in potential. ∆Φ ≤ rank(H') + 1 – trees(H). No new nodes become marked. no two trees have same rank after consolidation trees(H') ≤ rank(H') + 1. Amortized cost. O(log n). ĉ = c +∆Φ = O(rank(H)) + O(rank(H')). i i The rank of a Fibonacci heap with n elements is O(log n). Fibonacci lemma (stay tuned) Φ(H)  = trees(H) + 2 ⋅ marks(H) 36Fibonacci heap vs. binomial heaps Observation. If only INSERT and EXTRACTMIN operations, then all trees are binomial trees. we link only trees of equal rank B B B B 0 1 2 3 Binomial heap property. This implies rank(H) ≤ log n. 2 Fibonacci heap property. Our DECREASEKEY implementation will not preserve this property, but we will implement it in such a way that rank(H) ≤ log n. φ 37FIBONACCI HEAPS preliminaries ‣ insert ‣ extract the minimum ‣ decrease key ‣ bounding the rank ‣ meld and delete ‣ SECTION 19.3Fibonacci heap: decrease key Intuition for deceasing the key of node x. If heaporder is not violated, decrease the key of x. Otherwise, cut tree rooted at x and meld into root list. decreasekey of x from 30 to 7 6 8 29 10 44 30 23 22 48 31 17 45 32 24 50 55 39Fibonacci heap: decrease key Intuition for deceasing the key of node x. If heaporder is not violated, decrease the key of x. Otherwise, cut tree rooted at x and meld into root list. decreasekey of x from 23 to 5 6 7 8 29 10 45 32 44 55 23 22 48 31 17 24 50 40Fibonacci heap: decrease key Intuition for deceasing the key of node x. If heaporder is not violated, decrease the key of x. Otherwise, cut tree rooted at x and meld into root list. decreasekey of 22 to 4 decreasekey of 48 to 3 decreasekey of 31 to 2 6 7 5 decreasekey of 17 to 1 8 29 10 45 32 44 24 55 22 48 31 17 50 41Fibonacci heap: decrease key Intuition for deceasing the key of node x. If heaporder is not violated, decrease the key of x. Otherwise, cut tree rooted at x and meld into root list. Problem: number of nodes not exponential in rank. 6 7 5 4 3 2 1 8 29 10 45 32 44 24 50 rank = 4, nodes = 5 55 42Fibonacci heap: decrease key Intuition for deceasing the key of node x. If heaporder is not violated, decrease the key of x. Otherwise, cut tree rooted at x and meld into root list. Solution: as soon as a node has its second child cut, cut it off also and meld into root list (and unmark it). min 7 18 38 marked node: 24 17 23 21 39 41 one child already cut 26 46 30 52 35 88 72 43Fibonacci heap: decrease key Case 1. heap order not violated Decrease key of x. Change heap min pointer (if necessary). decreasekey of x from 46 to 29 min 7 18 38 24 17 23 21 39 41 26 46 30 52 x 35 88 72 44Fibonacci heap: decrease key Case 1. heap order not violated Decrease key of x. Change heap min pointer (if necessary). decreasekey of x from 46 to 29 min 7 18 38 24 17 23 21 39 41 26 29 30 52 x 35 88 72 45Fibonacci heap: decrease key Case 2a. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 29 to 15 min 7 18 38 24 17 23 21 39 41 p 26 29 30 52 x 35 88 72 46Fibonacci heap: decrease key Case 2a. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 29 to 15 min 7 18 38 24 17 23 21 39 41 p 26 15 30 52 x 35 88 72 47Fibonacci heap: decrease key Case 2a. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 29 to 15 min 7 18 38 24 17 23 21 39 41 p 26 15 30 52 x 35 88 72 48Fibonacci heap: decrease key Case 2a. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 29 to 15 min x 15 7 18 38 72 24 17 23 21 39 41 p 26 30 52 35 88 49Fibonacci heap: decrease key Case 2a. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 29 to 15 min x 15 7 18 38 72 24 24 17 23 21 39 41 p 26 30 52 35 88 50Fibonacci heap: decrease key Case 2b. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 35 to 5 min 15 7 18 38 72 24 24 17 23 21 39 41 p 26 30 52 35 88 x 51Fibonacci heap: decrease key Case 2b. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 35 to 5 min 15 7 18 38 72 24 24 17 23 21 39 41 p 26 30 52 5 88 x 52Fibonacci heap: decrease key Case 2b. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 35 to 5 x min 15 5 7 18 38 72 24 24 17 23 21 39 41 p 26 30 52 88 53Fibonacci heap: decrease key Case 2b. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 35 to 5 x min 15 5 7 18 38 72 24 24 17 23 21 39 41 second child cut p 26 30 52 88 54Fibonacci heap: decrease key Case 2b. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 35 to 5 x min p 15 5 26 7 18 38 72 88 24 24 17 23 21 39 41 30 52 55Fibonacci heap: decrease key Case 2b. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 35 to 5 x min p 15 5 26 7 18 38 p' 72 88 24 24 17 23 21 39 41 second child cut 30 52 56Fibonacci heap: decrease key Case 2b. heap order violated Decrease key of x. Cut tree rooted at x, meld into root list, and unmark. If parent p of x is unmarked (hasn't yet lost a child), mark it; Otherwise, cut p, meld into root list, and unmark (and do so recursively for all ancestors that lose a second child). decreasekey of x from 35 to 5 x min p p' p'' 15 5 26 24 7 18 38 but don't 72 88 17 23 21 39 41 mark parent if it's a root 30 52 57Fibonacci heap: decrease key analysis Actual cost. c = O(c), where c is the number of cuts. i O(1) time for changing the key. O(1) time for each of c cuts, plus melding into root list. Change in potential. ∆Φ = O(1) – c. trees(H') = trees(H) + c. each cut (except first) unmarks a node marks(H') ≤ marks(H) – c + 2. last cut may or may not mark a node ΔΦ ≤ c + 2 ⋅ (c + 2) = 4 – c. Amortized cost. ĉ = c + ∆Φ = O(1). i i Φ(H)  = trees(H) + 2 ⋅ marks(H) 58FIBONACCI HEAPS preliminaries ‣ insert ‣ extract the minimum ‣ decrease key ‣ bounding the rank ‣ meld and delete ‣ SECTION 19.4Analysis summary Insert. O(1). Deletemin. O(rank(H)) amortized. Decreasekey. O(1) amortized. Fibonacci lemma. Let H be a Fibonacci heap with n elements. Then, rank(H) = O(log n). number of nodes is exponential in rank 60Bounding the rank Lemma 1. Fix a point in time. Let x be a node of rank k, and let y , …, y 1 k denote its current children in the order in which they were linked to x. Then: x 0B7 i=1 rank(y ) i i 2B7 i 2 y y … y 1 2 k Pf. When y was linked into x, x had at least i – 1 children y , …, y . – i 1 i 1 Since only trees of equal rank are linked, at that time rank(y )  = rank(x) ≥ i – 1. i Since then, y has lost at most one child (or y would have been cut). i i Thus, right now rank(y ) ≥ i – 2. ▪ i 61Bounding the rank Lemma 1. Fix a point in time. Let x be a node of rank k, and let y , …, y 1 k denote its current children in the order in which they were linked to x. Then: x 0B7 i=1 rank(y ) i i 2B7 i 2 y y … y 1 2 k Def. Let T be smallest possible tree of rank k satisfying property. k T T T T T T 0 1 2 3 4 5 F = 1 F = 2 F = 3 F = 5 F = 8 F = 13 2 3 4 5 6 7 62Bounding the rank Lemma 1. Fix a point in time. Let x be a node of rank k, and let y , …, y 1 k denote its current children in the order in which they were linked to x. Then: x 0B7 i=1 rank(y ) i i 2B7 i 2 y y … y 1 2 k Def. Let T be smallest possible tree of rank k satisfying property. k T T T 6 4 5 F = 8 F = 13 F = F + F = 8 + 13 = 21 6 7 8 6 7 63Bounding the rank Lemma 2. Let s be minimum number of elements in any Fibonacci heap of k th rank k. Then s ≥ F , where F is the k Fibonacci number. k+2 k k Pf. by strong induction on k Base cases: s = 1 and s = 2. 0 1 Inductive hypothesis: assume s ≥ F for i = 0, …, k – 1. i+2 i As in Lemma 1, let let y , …, y denote its current children in the order in 1 k which they were linked to x. (Lemma 1) s ≥ 1 + 1 + (s + s + … + s ) k 0 1 k–2 (inductive hypothesis) ≥ (1 + F ) + F + F + … + F 1 2 3 k (Fibonacci fact 1) = F . ▪ k+2 64Bounding the rank Fibonacci lemma. Let H be a Fibonacci heap with n elements. Then, rank(H) ≤ log n, where φ is the golden ratio = (1 + √5) / 2 ≈ 1.618. φ Pf. Let H is a Fibonacci heap with n elements and rank k. k Then n ≥ F ≥ φ . k+2 Lemma 2 Fibonacci Fact 2 Taking logs, we obtain rank(H) = k ≤ log n. ▪ φ 65Fibonacci fact 1 Def. The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, … 0B7 k=0 F = 1B7 k=1 k F +FB7 k 2 k 1 k 2 Fibonacci fact 1. For all integers k ≥ 0, F = 1 + F + F + … + F . 0 1 k k+2 Pf. by induction on k Base case: F = 1 + F = 2. 0 2 Inductive hypothesis: assume F = 1 + F + F + … + F . 0 1 k–1 k+1 (definition) F = F + F k+2 k k+1 (inductive hypothesis) = F + (1 + F + F + … + F ) k 0 1 k–1 (algebra) = 1 + F + F + … + F + F . ▪ 0 1 k–1 k 66Fibonacci fact 2 Def. The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, … 0B7 k=0 F = 1B7 k=1 k F +FB7 k 2 k 1 k 2 k Fibonacci fact 2. F ≥ φ , where φ = (1 + √5) / 2 ≈ 1.618. k+2 Pf. by induction on k Base cases: F = 1 ≥ 1, F = 2 ≥ φ. 2 3 k k + 1 Inductive hypotheses: assume F ≥ φ and F ≥ φ k k+1 (definition) F = F + F k+2 k k+1 k – 1 k – 2 (inductive hypothesis) ≥ φ + φ k – 2 (algebra) = φ (1 + φ) 2 k – 2 2 (φ = φ + 1) = φ φ k (algebra) = φ . ▪ 67Fibonacci numbers and nature Fibonacci numbers arise both in nature and algorithms. pinecone cauliflower 68FIBONACCI HEAPS preliminaries ‣ insert ‣ extract the minimum ‣ decrease key ‣ bounding the rank ‣ meld and delete ‣ SECTION 19.2, 19.3Fibonacci heap: meld Meld. Combine two Fibonacci heaps (destroying old heaps). Recall. Root lists are circular, doublylinked lists. min min 23 24 17 7 3 21 30 26 46 18 52 41 heap H1 heap H2 35 44 39 70Fibonacci heap: meld Meld. Combine two Fibonacci heaps (destroying old heaps). Recall. Root lists are circular, doublylinked lists. min 23 24 17 7 3 21 30 26 46 18 52 41 35 heap H 44 39 71Fibonacci heap: meld analysis Actual cost. c = O(1). i Change in potential. ∆Φ = 0. Amortized cost. ĉ = c + ∆Φ = O(1). i i Φ(H)  = trees(H) + 2 ⋅ marks(H) min 23 24 17 7 3 21 30 26 46 18 52 41 35 heap H 44 39 72Fibonacci heap: delete Delete. Given a handle to an element x, delete it from heap H. DECREASEKEY(H, x, ∞). EXTRACTMIN(H). Amortized cost. ĉ = O(rank(H)). i O(1) amortized for DECREASEKEY. O(rank(H)) amortized for EXTRACTMIN. Φ(H)  = trees(H) + 2 ⋅ marks(H) 73Priority queues performance cost summary operation linked list binary heap binomial heap Fibonacci heap † MAKEHEAP O(1) O(1) O(1) O(1) ISEMPTY O(1) O(1) O(1) O(1) INSERT O(1) O(log n) O(log n) O(1) EXTRACTMIN O(n) O(log n) O(log n) O(log n) DECREASEKEY O(1) O(log n) O(log n) O(1) DELETE O(1) O(log n) O(log n) O(log n) MELD O(1) O(n) O(log n) O(1) FINDMIN O(n) O(1) O(log n) O(1) † amortized Accomplished. O(1) INSERT and DECREASEKEY, O(log n) EXTRACTMIN. 74PRIORITY QUEUES binary heaps ‣ dary heaps ‣ binomial heaps ‣ Fibonacci heaps ‣ advanced topics ‣Heaps of heaps bheaps. Fat heaps. 23 heaps. Leaf heaps. Thin heaps. Skew heaps. Splay heaps. Weak heaps. Leftist heaps. Quake heaps. Pairing heaps. Violation heaps. Runrelaxed heaps. Rankpairing heaps. Skewpairing heaps. Rankrelaxed heaps. Lazy Fibonacci heaps. 76Brodal queues Q. Can we achieve same running time as for Fibonacci heap but with worstcase bounds per operation (instead of amortized) Theory. Brodal 1996 Yes. Practice. Ever implemented Constants are high (and requires RAM model). 77Strict Fibonacci heaps Q. Can we achieve same running time as for Fibonacci heap but with worstcase bounds per operation (instead of amortized) in pointer model Theory. BrodalLagogiannisTarjan 2012 Yes. StrictFibonacci Heaps StrictFibonacci Heaps † GerthStølting Brodal George Lagogiannis Robert E. Tarjan ∗ MADALGO Agricultural University Dept.of ComputerScience Dept. ofComputer Science ofAthens Princeton University † GerthStølting Brodal George Lagogiannis Robert E. Tarjan Aarhus University IeraOdos75, 11855 Athens and HPLabs ∗ MADALGO Agricultural University Dept.of ComputerScience Greece 35 OldenStreet, Princeton Åbogade 34, 8200Aarhus N Dept. ofComputer Science ofAthens Princeton University lagogianaua.gr NewJersey08540, USA Denmark Aarhus University IeraOdos75, 11855 Athens and HPLabs retcs.princeton.edu gerthcs.au.dk Greece 35 OldenStreet, Princeton Åbogade 34, 8200Aarhus N lagogianaua.gr NewJersey08540, USA Denmark ABSTRACT 1. INTRODUCTION retcs.princeton.edu gerthcs.au.dk Williams in 1964 introducedbinaryheaps25. Sincethen Wepresentthefirstpointerbasedheapimplementationwith the design and analysis of heaps has been thoroughly inves time boundsmatchingthose of Fibonacci heapsin theworst ABSTRACT 1. INTRODUCTION tigated. The most common operations supported by the case. We support makeheap, insert, findmin, meld and Williams in 1964 introducedbinaryheaps25. Sincethen Wepresentthefirstpointerbasedheapimplementationwith heaps in the literature are those listed below. We assume decreasekey in worstcase O(1) time, and delete and delete the design and analysis of heaps has been thoroughly inves time boundsmatchingthose of Fibonacci heapsin theworst that each item stored contains an associated key. No item min in worstcase O(lgn)time,where n is the size of the tigated. The most common operations supported by the case. We support makeheap, insert, findmin, meld and can be in more than one heap at a time. heap. The data structure uses linear space. heaps in the literature are those listed below. We assume decreasekey in worstcase O(1) time, and delete and delete Aprevious,verycomplicated,solutionachievingthesame that each item stored contains an associated key. No item min in worstcase O(lgn)time,mawhkeerheenapis()thCr e seiz ateeof a nthew, e empty heap and return a ref time boundsin theRAMmodel madeessential useof arrays can be in more than one heap at a time. heap. The data structure uses linear sepa renccee. to it. and extensive use of redundantcounter schemesto maintain Aprevious,verycomplicated,solutionachievingthesame balance. Our solution uses neither. Our key simplification insert(H,i) Insert item i,notcma urrkeenhtleyaipn()aCrheeaapt,i e antnoew, empty heap and return a ref time boundsin theRAMmodel madeessential useof arrays is to discard the structure of the smaller heap when doing heap H,andreturnareferenceteorenwcheerteo iit.is stored and extensive use of redundantcounter schemesto maintain ameld. Weusethepigeonholeprincipleinplaceofthe in H. balance. Our solution uses neither. Our key simplification insert(H,i) Insert item i,notcurrentlyinaheap,into redundant counter mechanism. is to discard the structure of the smaller heap when doing meld(H ,H ) Return a reference to a he neawphH ea,a p cnodntraeintuinrgnareferencetowhere i is stored 1 2 ameld. Weusethepigeonholeprincipleinplaceofthe all items in the two heaps H1 an indHH.2 (H1 and H2 CategoriesandSubjectDescriptors redundant counter mechanism. cannot be accessed after meld). E.1 Data Structures: Trees; F.2.2 Theory of Compu meld(H ,H ) Return a reference to a new heap containing 1 2 findmin(H) Return a reference to where the item with tation: AnalysisofAlgorithmsandProblem Complexity— all items in the two heaps H1 and H2 (H1 and H2 CategoriesandSubjectDescriptors minimum key is stored in the heaca p H nn.ot be accessed after meld). Nonnumerical Algorithms and Problems E.1 Data Structures: Trees; F.2.2 Theory of Compu deletemin(H) Delete the itemfind withmmin( iniH mu)mRekteuyrnfroamreference to where the item with tation: AnalysisofAlgorithmsandProblem Complexity— 78 GeneralTerms the heap H. minimum key is stored in the heap H. Nonnumerical Algorithms and Problems Algorithms delete(H,e) Delete an item fromdetlheetehem apin( HHgiv ) eDe nlaetreefthe item with minimum key from GeneralTerms erence e to where it is stored. the heap H. Keywords Algorithms decreasekey(H,e,k) Decrease de thelekteey(H, ofet)heDe itleem tegainveintem from the heap H given a ref Data structures, heaps, meld, decreasekey, worstcase com by the reference e in heap H to theerennecw e eketo y kw.here it is stored. plexity Keywords decreasekey(H,e,k) Decrease the key of the item given There are many heap implementations in the literature, Data structures, heaps, meld, decreasekey, worstcase com by the reference e in heap H to the new key k. with a variety of characteristics. We can divide them into plexity ∗ two main categories, dependingon whetherthe time bounds CenterforMassiveDataAlgorithmics,aCenteroftheDan There are many heap implementations in the literature, are worst case or amortized. Most of the heaps in the lit ish National Research Foundation. with a variety of characteristics. We can divide them into † erature are based on heapordered trees, i.e. tree structures Partially supported by NSF grant CCF0830676, USIsrael ∗ two main categories, dependingon whetherthe time bounds Binational Science Foundation GCe ranntter2006204, forMassivan edDatthaeAlgoritwh hmeirces,thaeCe itnem tersotofrtehdeiDnaannode has a key not smaller than are worst case or amortized. Most of the heaps in the lit ish National Research Foundation. Distinguished Visitor Program of the Stanford University the key of the item stored in its parent. Heapordered trees † erature are based on heapordered trees, i.e. tree structures Computer Science Department. The information contained Partially supported by NSF grant CCF0830676, USIsrael give heap implementations that achieve logarithmic time for herein does not necessarily reflect the opinion or policy of Binational Science Foundation Grant 2006204, and the where the item stored in a node has a key not smaller than all the operations. Early examples are the implicit binary the federal government and no official endorsement should Distinguished Visitor Program of the Stanford University the key of the item stored in its parent. Heapordered trees heapsofWilliams25, theleftist heapsofCrane5asmodi be inferred. Computer Science Department. The information contained give heap implementations that achieve logarithmic time for fiedbyKnuth20, and thebinomialheapsof Vuillemin24. herein does not necessarily reflect the opinion or policy of all the operations. Early examples are the implicit binary The introduction of Fibonacci heaps 15 by Fredman and the federal government and no official endorsement should heapsofWilliams25, theleftist heapsofCrane5asmodi be inferred. Tarjan was a breakthrough since they achieved O(1) amor fiedbyKnuth20, and thebinomialheapsof Vuillemin24. tized time for all the operations above except for delete and Permission to make digital or hard copies of all or part of thisworkfor The introduction of Fibonacci heaps 15 by Fredman and deletemin, which require O(lgn) amortized time, where n personal or classroom use is granted without fee provided that copies are Tarjan was a breakthrough since they achieved O(1) amor not made or distributed for profit or commercial advantage andthatcopies is the number of items in the heap and lg the basetwo log tized time for all the operations above except for delete and bear this notice and thefull citation on the firstpage. Tocopyotherwise,to Permission to make digital or hard copies of all or part of thisworkfor arithm. The drawback of Fibonacci heaps is that they are republish, topostonserversortoredistribute tolists,requires priorspecific deletemin, which require O(lgn) amortized time, where n personal or classroom use is granted without fee provided that copies are complicated compared to existing solutions and not as ef permission and/or afee. not made or distributed for profit or commercial advantage andthatcopies is the number of items in the heap and lg the basetwo log ficient in practice as other, theoretically less efficient solu STOC.12, May 19–22, 2012, New York,Nbe ewarYtohirks,not USicAe.and thefull citation on the firstpage. Tocopyotherwise,to arithm. The drawback of Fibonacci heaps is that they are tions. Thus, Fibonacci heaps opened the way for further Copyright 2012 ACM 9781450312455/12/05 ...10.00. republish, topostonserversortoredistribute tolists,requires priorspecific complicated compared to existing solutions and not as ef permission and/or afee. ficient in practice as other, theoretically less efficient solu STOC.12, May 19–22, 2012, New York,New York, USA. tions. Thus, Fibonacci heaps opened the way for further Copyright 2012 ACM 9781450312455/12/05 ...10.00.Fibonacci heaps: practice Q. Are Fibonacci heaps useful in practice A. They are part of LEDA and Boost C++ libraries. (but other heaps seem to perform better in practice) 79Pairing heaps Pairing heap. A selfadjusting heapordered general tree. Theory. Same amortized running times as Fibonacci heaps for all operations except DECREASEKEY. O(log n) amortized. Fredman et al. 1986 Ω(log log n) lower bound on amortized cost. Fredman 1999 O(loglogn) amortized. Pettie 2005 2 80Pairing heaps Pairing heap. A selfadjusting heapordered general tree. Practice. As fast as (or faster than) the binary heap on some problems. Included in GNU C++ library and LEDA. RESEARCH CONlRlWlIONS Algorithms and Data Structures Pairing Heaps: G. Scott Graham Editor Experiments and Analysis JOHN T. STASKO and JEFFREY SCOTT VlllER ABSTRACT: The pairing heap has recently been and practical importance from their use in solving a introduced as a new data structure for priority queues. wide range of combinatorial problems, including job Pairing heaps are extremely simple to implement and scheduling, minimal spanning tree, shortest path, seem to be very efficient in practice, but they are difficult and graph traversal. to analyze theoretically, and open problems remain. It Priority queues support the operations insert, has been conjectured that they achieve the same findmin, and deletemin; additional operations often amortized time bounds as Fibonacci heaps, namely, include decreasekey and delete. The insert(t, v) opera O(log n) time for delete and deletemin and O(1) for tion adds item t with key value v to the priority all other operations, where n is the size of the priority queue. The findmin operation returns the item queue at the time of the operation. We provide empirical with minimum key value. The deletemin operation evidence that supports this conjecture. The most returns the item with minimum key value and promising algorithm in our simulations is a new variant removes it from the priority queue. The decrease of the twopass method, called auxiliary twopass. We key(t, d) operation reduces item t’s key value by d. prove that, assuming no decreasekey operations are The delete(t) operation removes item t from the performed, it achieves the same amortized time bounds as priority queue. The decreasekey and delete opera Fibonacci heaps. tions require that a pointer to the location in the priority queue of item t be supplied explicitly, since 1. INTRODUCTION priority queues do not support searching for arbi A priority queue is an abstract data type for main trary items by value. Some priority queues also sup taining and manipulating a set of items based on port the merge operation, which combines two item 81 priority I. Prio’rity queues derive great theoretical disjoint priority queues. We will concentrate on the insert, deletemin, and Support was provided in part by NSF research grant DCR8403613, an NSF Presidential Young Investigator Award, an IBM Faculty Development Award, decreasekey operations because they are the opera and a Guggenheim Fellowship. tions that primarily distinguish priority queues from Part of this research was performed at Mathematical Sciences Research Insti other set manipulation algorithms and because they tute. Berkeley, Calif., and the Institut National de Recherche en Informatique et en Automatique, Rocquencourt. France. are the critical operations as far as the time bounds 0 1987 ACM OOOl0782/87/03000234 75a: are concerned. Communications of the ACM March 1987 Volume 30 Number 3 Priority queues performance cost summary binomial pairing Fibonacci Brodal operation linked list binary heap heap heap † heap † queue MAKEHEAP O(1) O(1) O(1) O(1) O(1) O(1) ISEMPTY O(1) O(1) O(1) O(1) O(1) O(1) INSERT O(1) O(log n) O(log n) O(1) O(1) O(1) EXTRACTMIN O(n) O(log n) O(log n) O(log n) O(log n) O(log n) DECREASEKEY O(loglogn) O(1) O(log n) O(log n) O(1) O(1) 2 DELETE O(1) O(log n) O(log n) O(log n) O(log n) O(log n) MELD O(1) O(n) O(log n) O(1) O(1) O(1) FINDMIN O(n) O(1) O(log n) O(1) O(1) O(1) † amortized 82Priority queues with integer priorities Assumption. Keys are integers between 0 and C. Theorem. Thorup 2004 There exists a priority queue that supports INSERT, FINDMIN, and DECREASEKEY in constant time and EXTRACTMIN and DELETEKEY in either O(log log n) or O(log log C) time. ARTICLE IN PRESS Journal of Computer and System Sciences 69 (2004) 330–353 http://www.elsevier.com/locate/jcss Integer priority queues with decrease key in constant time and the single source shortest paths problem Mikkel Thorup ATT Labs Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ 07932, USA Received 22 July 2003; revised 8 March 2004 Available online 20 July 2004 Abstract We consider Fibonacci heap style integer priority queues supporting findmin, insert, and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys supports delete in OðloglognÞ time. If the integers are in the range ½0;NÞ; we can also support delete in OðloglogNÞ time. Even for the special case of monotone priority queues, where the minimum has to be nondecreasing, the 1=ð3eÞ 1=ð4eÞ best previous bounds on delete were OððlognÞ Þ and OððlogNÞ Þ: These previous bounds used bothrandomization andamortization. Our new bounds aredeterministic,worstcase,withnorestriction to monotonicity, and exponentially faster. 83 As a classical application, for a directed graph with n nodes and m edges with nonnegative integer weights, we get single source shortest paths in OðmþnloglognÞ time, or OðmþnloglogCÞ if C is the maximaledgeweight.ThelattersolvesanopenproblemofAhuja,Mehlhorn,Orlin,andTarjanfrom1990. r 2004 Elsevier Inc. All rights reserved. Keywords: Integer priority queues; Decrease key; Fibonacci heaps; Single source shortest paths 1. Introduction In 1984, Fredman and Tarjan introduced Fibonacci heaps 15, which is a priority queue over a dynamic ordered set H supporting the following operations: findminðHÞ Returns an element from H with minimum key value in constant time. insertðH;aÞ Adds the element a to H in constant time. deckeyðH;a;xÞ Reduces the key value of element a to x in constant time. If the current key value of a was smaller than x; it is an error. Email address: mthorupresearch.att.com. 00220000/see front matterr 2004 Elsevier Inc. All rights reserved. doi:10.1016/j.jcss.2004.04.003Priority queues with integer priorities Assumption. Keys are integers between 0 and C. Theorem. Thorup 2004 There exists a priority queue that supports INSERT, FINDMIN, and DECREASEKEY in constant time and EXTRACTMIN and DELETEKEY in either O(log log n) or O(log log C) time. Corollary 1. Can implement Dijkstra's algorithm in either O(m log log n) or O(m log log C) time. Corollary 2. Can sort n integers in O(n log log n) time. Computational model. Word RAM. 84Soft heaps Goal. Break informationtheoretic lower bound by allowing priority queue to corrupt 10 of the keys (by increasing them). elements inserted 0 11 22 44 55 88 11 22 99 44 33 77 66 0 55 57 66 77 88 99 soft heap corrupted 85Soft heaps Goal. Break informationtheoretic lower bound by allowing priority queue to corrupt 10 of the keys (by increasing them). Representation. Set of binomial trees (with some subtrees missing). Each node may store several elements. Each node stores a value that is an upper bound on the original keys. Binomial trees are heapordered with respect to these values. 86Soft heaps Goal. Break informationtheoretic lower bound by allowing priority queue to corrupt 10 of the keys (by increasing them). Theorem. Chazelle 2000 Starting from an empty soft heap, any sequence of n INSERT, MIN, EXTRACTMIN, MELD, and DELETE operations takes O(n) time and at most 10 of its elements are corrupted at any given time. The Soft Heap: An Approximate Priority Queue with Optimal Error Rate BERNARD CHAZELLE Princeton University, Princeton, New Jersey, and NEC Research Institute Abstract. A simple variant of a priority queue, called a soft heap,isintroduced.Thedatastructure supports the usual operations: insert, delete, meld, and findmin. Its novelty is to beat the logarithmic bound on the complexity of a heap in a comparisonbased model. To break this informationtheoretic barrier, the entropy of the data structure is reduced by artificially raising the values of certain keys. Given any mixed sequence of n operations, a soft heap with error rate (for any 0" 1/2) ensures that, at any time, at most n of its items have their keys raised. The amortized complexity of each operation is constant, except for insert, which takes O(log 1/)time.Thesoftheapisoptimalforany value of in a comparisonbased model. The data structure is purely pointerbased. No arrays are used and no numeric assumptions are made on the keys. The main idea behind the soft heap is to move items across the data structure not individually, as is customary, but in groups, in a datastructuring equivalent of “car pooling.” Keys must be raised as a result, in order to preserve the heap ordering of the data structure. The soft heap can be used to compute exact or approximate medians and percentiles optimally. It is also useful for approximate sorting and for computing minimum spanning trees of general graphs. Categories and Subject Descriptors: E.1 Data Structures: Nonnumerical Algorithms and Problems 87 General Terms: Theory Additional Key Words and Phrases: Amortization, heap, priority queue, soft heap 1. Introduction We design a simple variant of a priority queue, called a soft heap.Thedata structure stores items with keys from a totally ordered universe, and supports the operations: ApreliminaryversionofthispaperasCHAZELLE,B.1998.Carpoolingasadatastructuringdevice: The soft heap. In Proceedings of the 6th Annual European Symposium on Algorithms,pp.35–42. This work was supported in part by National Science Foundation (NSF) Grants CCR 9301254 and CCR 9623768, ARO Grant DAAH049610181, and NEC Research Institute. Author’s address: Department of Computer Science, Princeton University, 35 Olden Street, Prince ton, NJ 085442087, email: chazellecs.princeton.edu or NEC Research Institute, email: chazelle research.nj.nec.com. Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. ©2000ACM00045411/00/1100101205.00 Journal of the ACM, Vol. 47, No. 6, November 2000, pp. 1012–1027.Soft heaps Goal. Break informationtheoretic lower bound by allowing priority queue to corrupt 10 of the keys (by increasing them). Q. Brilliant. But how could it possibly be useful th Ex. Lineartime deterministic selection. To find k smallest element: Insert the n elements into soft heap. Extract the minimum element n / 2 times. The largest element deleted ≥ 4n / 10 elements and ≤ 6n / 10 elements. Can remove ≥ 4n / 10 of elements and recur. T(n) ≤ T(3n / 5) + O(n) ⇒ T(n) = O(n). ▪ 88Soft heaps Theorem. Chazelle 2000 There exists an O(m α(m, n)) time deterministic algorithm to compute an MST in a graph with n nodes and m edges. Algorithm. Borůvka + nongreedy + divideandconquer + soft heap + … AMinimumSpanningTreeAlgorithmwithInverse Ackermann Type Complexity BERNARD CHAZELLE Princeton University, Princeton, New Jersey, and NEC Research Institute Abstract. A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m(m, n)), where is the classical functional inverse of Ackermann’s function and n (respectively, m)isthenumberofvertices(respectively,edges).The algorithm is comparisonbased: it uses pointers, not arrays, and it makes no numeric assumptions on the edge costs. Categories and Subject Descriptors: F.2.2 Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms and Problems. General Terms: Theory Additional Key Words and Phrases: Graphs, matroids, minimum spanning trees 89 1. Introduction The history of the minimum spanning tree (MST)problemislongandrich,going as far back as Boru˚vka’s work in 1926 Boru˚vka 1926; Graham and Hell 1985; Nesˇetˇi r l 1997. In fact, MST is perhaps the oldest open problem in computer science. According to Nesˇetˇi r l 1997, “this is a cornerstone problem of combina torial optimization and in a sense its cradle.” Textbook algorithms run in O(m log n)time,where n and m denote, respectively, the number of vertices and edges in the graph. Improvements to O(m log log n)weregivenindependently by Yao 1975 and by Cheriton and Tarjan 1976. In the mideighties, Fredman and Tarjan 1987 lowered the complexity to O(m"(m, n)), where "(m, n)is the number of logiterations necessary to map n to a number less than m/n.In the worst case, m O(n)andtherunningtimeis O(m log m). Soon after, the ApreliminaryversionofthispaperappearedasCHAZELLE,B.1997.Afasterdeterministicalgorithm for minimum spanning trees. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science.IEEEComputerSocietyPress,LosAlamitos,Calif.,pp.22–31. This work was supported in part by the National Science Foundation (NSF) Grants CCR 9301254 and CCR 9623768, ARO Grant DAAH049610181, and NEC Research Institute. Author’s address: Department of Computer Science, Princeton University, 35 Olden Street, Prince ton, NJ 083442087, email: chazellecs.princeton.edu and NEC Research Institute, email: chazelleresearch.nj.nec.com. Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery (ACM), Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. ©2000ACM00045411/00/1100102805.00 Journal of the ACM, Vol. 47, No. 6, November 2000, pp. 1028–1047.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.TomHunt
User Type:
Teacher
Country:
United States
Uploaded Date:
22-07-2017