Fibonacci heaps ppt

fibonacci heaps in data structures ppt and fibonacci heap data structure
Dr.TomHunt Profile Pic
Dr.TomHunt,United States,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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/kleinberg-tardos Last updated on Sep 8, 2013 7:00 AMPriority queues performance cost summary operation linked list binary heap binomial heap Fibonacci heap † MAKE-HEAP O(1) O(1) O(1) O(1) IS-EMPTY O(1) O(1) O(1) O(1) INSERT O(1) O(log n) O(log n) O(1) EXTRACT-MIN O(n) O(log n) O(log n) O(log n) DECREASE-KEY 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) FIND-MIN O(n) O(1) O(log n) O(1) † amortized Ahead. O(1) INSERT and DECREASE-KEY, O(log n) EXTRACT-MIN. 2Fibonacci heaps Theorem. Fredman-Tarjan 1986 Starting from an empty Fibonacci heap, any sequence of m INSERT, EXTRACT-MIN, and DECREASE-KEY 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 AT&T 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 F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in qlogn) amortized time and all other standard heap operations in o( 1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms. In particular, we obtain the following worst-case 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 single-source shortest path problem with nonnegative edge lengths, improved from O(m logfmh+2)n); (2) O(nlog n + nm) for the all-pairs 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 Problems-computations on 3 discrete structures; sorting and searching; G.2.2 Discrete Mathematics: Graph Theory-graph 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. 24-26). 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 82-0403 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, AT&T 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 0004-541 l/87/0700-0596 1.50 Journal ofthe Association for Computing Machinery, Vol. 34, No. 3, July 1987, Pages 596-615. Fibonacci heaps Theorem. Fredman-Tarjan 1986 Starting from an empty Fibonacci heap, any sequence of m INSERT, EXTRACT-MIN, and DECREASE-KEY 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 best-known bounds for all-pairs 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 DECREASE-KEY by repeatedly exchanging node with its parent. Fibonacci heap: lazily defer consolidation until next EXTRACT-MIN; implement DECREASE-KEY 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 heap-ordered trees. each child no smaller than its parent heap-ordered tree 17 24 23 7 3 root 30 26 46 18 52 41 heap H 35 44 39 7Fibonacci heap: structure Set of heap-ordered 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, doubly-linked 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 doubly-linked 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 heap-ordered 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 20