Question? Leave a message!




Priority queue data type

Priority queue data type
PRIORITY QUEUES binary heaps ‣ dary heaps ‣ binomial heaps ‣ Fibonacci heaps ‣ Lecture slides by Kevin Wayne Copyright © 2005 PearsonAddison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on Sep 8, 2013 7:00 AMPriority queue data type A minoriented priority queue supports the following core operations: MAKEHEAP(): create an empty heap. INSERT(H, x): insert an element x into the heap. EXTRACTMIN(H): remove and return an element with the smallest key. DECREASEKEY(H, x, k): decrease the key of element x to k. The following operations are also useful: ISEMPTY(H): is the heap empty FINDMIN(H): return an element with smallest key. DELETE(H, x): delete element x from the heap. MELD(H , H ): replace heaps H and H with their union. 1 2 1 2 Note. Each element contains a key (duplicate keys are permitted) from a totallyordered universe. 2Priority queue applications Applications. A search. Heapsort. Online median. Huffman encoding. Prim's MST algorithm. Discrete eventdriven simulation. Network bandwidth management. Dijkstra's shortestpaths algorithm. … http://younginc.site11.com/source/5895/fos0092.html 3PRIORITY QUEUES binary heaps ‣ dary heaps ‣ binomial heaps ‣ Fibonacci heaps ‣ Algorithms FOUR TH EDITION ROBERT SEDGEWICK KEVIN WAYNE SECTION 2.4Complete binary tree Binary tree. Empty or node with links to two disjoint binary trees. Complete tree. Perfectly balanced, except for bottom level. complete tree with n = 16 nodes (height = 4) Property. Height of complete binary tree with n nodes is ⎣log n⎦. 2 Pf. Height increases (by 1) only when n is a power of 2. ▪ 5A complete binary tree in nature 6Binary heap Binary heap. Heapordered complete binary tree. Heapordered tree. For each child, the key in child ≥ key in parent. 6 parent 10 8 child child 12 18 11 25 21 17 19 7Explicit binary heap Pointer representation. Each node has a pointer to parent and two children. Maintain number of elements n. Maintain pointer to root node. Can find pointer to last node or next node in O(log n) time. root 6 10 8 12 18 11 25 21 17 19 last next 8Implicit binary heap Array representation. Indices start at 1. Take nodes in level order. Parent of node at k is at ⎣k / 2⎦. Children of node at k are at 2k and 2k + 1. 1 6 2 3 10 8 4 5 6 7 12 18 11 25 8 9 10 21 17 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 6 10 8 12 18 11 25 21 17 19 9Binary heap demo heap ordered 6 10 8 12 18 11 25 21 17 19 10Binary heap: insert Insert. Add element in new node at end; repeatedly exchange new element with element in its parent until heap order is restored. 6 10 8 12 18 11 25 add key to heap 21 17 19 7 (violates heap order) 6 7 8 12 10 11 25 18 21 17 19 swim up 11Binary heap: extract the minimum Extract min. Exchange element in root node with last node; repeatedly exchange element in root with its smaller child until heap order is restored. element to 6 remove 7 8 12 10 11 25 exchange 18 21 17 19 with root sink down violates 18 7 heap order 10 7 8 8 12 10 11 25 12 18 11 25 remove 21 17 19 6 21 17 19 6 from heap 12Binary heap: decrease key Decrease key. Given a handle to node, repeatedly exchange element with its parent until heap order is restored. decrease key of node x to 11 6 10 8 12 18 11 25 21 17 19 x 13Binary heap: analysis Theorem. In an implicit binary heap, any sequence of m INSERT, EXTRACTMIN, and DECREASEKEY operations with n INSERT operations takes O(m log n) time. Pf. Each heap op touches nodes only on a path from the root to a leaf; the height of the tree is at most log n. 2 The total cost of expanding and contracting the arrays is O(n). ▪ Theorem. In an explicit binary heap with n nodes, the operations INSERT, DECREASEKEY, and EXTRACTMIN take O(log n) time in the worst case. 14Binary heap: findmin Find the minimum. Return element in the root node. root 6 7 10 12 8 11 25 21 17 9 15Binary heap: delete Delete. Given a handle to a node, exchange element in node with last node; either swim down or sink up the node until heap order is restored. delete node x or y 6 7 10 x 12 8 11 25 y 21 17 9 last 16Binary heap: meld Meld. Given two binary heaps H and H , merge into a single binary heap. 1 2 Observation. No easy solution: Ω(n) time apparently required. H 2 H 1 7 10 12 8 11 25 21 17 9 17Binary heap: heapify Heapify. Given n elements, construct a binary heap containing them. Observation. Can do in O(n log n) time by inserting each element. Bottomup method. For i = n to 1, repeatedly exchange the element in node i with its smaller child until subtree rooted at i is heapordered. 1 8 2 3 12 9 4 5 6 7 7 22 3 26 8 9 10 11 14 11 15 22 8 12 9 7 22 3 26 14 11 15 22 1 2 3 4 5 6 7 8 9 10 11 18Binary heap: heapify Theorem. Given n elements, can construct a binary heap containing those n elements in O(n) time. Pf. h+1 There are at most ⎡n / 2 ⎤ nodes of height h. The amount of work to sink a node is proportional to its height h. Thus, the total work is bounded by: log n log n 2 2 h+1 h n/2 h nh/2 log n log n log n log n logh=0 n logh=0 n 2 2 2 2 2 2 h+1 h h+1 h h+1 h n/2 h nh/2 n/2 h nh/2 n/2 h nh/2 k h i k 1 n h/2 h=0 h=0 h=0 h=0 h=0 h=0 =2 i k k 1 2 2 2 h=1 i=1 h h h n h/2 n h/2 n h/2 =2n ▪ 2 h=1 h=1 h=1 =2n =2n =2n Corollary. Given two binary heaps H and H containing n elements in total, 1 2 can implement MELD in O(n) time. 19Priority queues performance cost summary operation linked list binary heap MAKEHEAP O(1) O(1) ISEMPTY O(1) O(1) INSERT O(1) O(log n) EXTRACTMIN O(n) O(log n) DECREASEKEY O(1) O(log n) DELETE O(1) O(log n) MELD O(1) O(n) FINDMIN O(n) O(1) 20Priority queues performance cost summary Q. Reanalyze so that EXTRACTMIN and DELETE take O(1) amortized time † operation linked list binary heap binary heap MAKEHEAP O(1) O(1) O(1) ISEMPTY O(1) O(1) O(1) INSERT O(1) O(log n) O(log n) † EXTRACTMIN O(1) O(n) O(log n) DECREASEKEY O(1) O(log n) O(log n) † DELETE O(1) O(1) O(log n) MELD O(1) O(n) O(n) FINDMIN O(n) O(1) O(1) † amortized 21PRIORITY QUEUES binary heaps ‣ dary heaps ‣ binomial heaps ‣ Fibonacci heaps ‣ Algorithms FOUR TH EDITION ROBERT SEDGEWICK KEVIN WAYNE SECTION 2.4Complete dary tree dary tree. Empty or node with links to d disjoint dary trees. Complete tree. Perfectly balanced, except for bottom level. Fact. The height of a complete dary tree with n nodes is ≤ ⎡log n⎤. d 23dary heap dary heap. Heapordered complete dary tree. Heapordered tree. For each child, the key in child ≥ key in parent. 4 20 30 10 46 20 40 80 32 34 55 22 34 82 90 24dary heap: insert Insert. Add node at end; repeatedly exchange element in child with element in parent until heap order is restored. Running time. Proportional to height = O(log n). d 4 20 30 10 46 20 40 80 32 34 55 22 34 82 90 25dary heap: extract the minimum Extract min. Exchange root node with last node; repeatedly exchange element in parent with element in largest child until heap order is restored. Running time. Proportional to d ⨉ height = O(d log n). d 4 20 30 10 46 20 40 80 32 34 55 22 34 82 90 26dary heap: decrease key Decrease key. Given a handle to an element x, repeatedly exchange it with its parent until heap order is restored. Running time. Proportional to height = O(log n). d 4 20 30 10 46 20 40 80 32 34 55 22 34 82 90 27Priority queues performance cost summary operation linked list binary heap dary heap MAKEHEAP O(1) O(1) O(1) ISEMPTY O(1) O(1) O(1) INSERT O(1) O(log n) O(log n) d EXTRACTMIN O(n) O(log n) O(d log n) d DECREASEKEY O(1) O(log n) O(log n) d DELETE O(1) O(log n) O(d log n) d MELD O(1) O(n) O(n) FINDMIN O(n) O(1) O(1) 28PRIORITY QUEUES binary heaps ‣ dary heaps ‣ binomial heaps ‣ Fibonacci heaps ‣ ND CHAPTER 6 (2 EDITION)Priority queues performance cost summary operation linked list binary heap dary heap MAKEHEAP O(1) O(1) O(1) ISEMPTY O(1) O(1) O(1) INSERT O(1) O(log n) O(log n) d EXTRACTMIN O(n) O(log n) O(d log n) d DECREASEKEY O(1) O(log n) O(log n) d DELETE O(1) O(log n) O(d log n) d MELD O(1) O(n) O(n) FINDMIN O(n) O(1) O(1) Goal. O(log n) INSERT, DECREASEKEY, EXTRACTMIN, and MELD. mergeable heap 30Binomial heaps A priority queue is a set; each element of such a set has a name, which is used to uniquely identify the element, and a label or priority drawn from a totally ordered set. Elements of the priority queue can be Programming S.L. Graham, R.L. Rivest thought of as awaiting service, where the item with the Techniques Editors smallest label is always to be served next. Ordinary stacks and queues are special cases of priority queues. A Data Structure for A variety of applications directly require using prior ity queues: job scheduling, discrete simulation languages Manipulating Priority where labels represent the time at which events are to occur, as well as various sorting problems. These are Queues discussed, for example, in 2, 3, 5, 11, 15, 17, 24. Priority queues also play a central role in several good algorithms, Jean Vuillemin such as optimal code constructions, Chartre's prime Universit6 de ParisSud number generator, and Brown's power series multipli cation (see 16 and 17); applications have also been found in numerical analysis algorithms 10, 17, 19 and in graph algorithms for such problems as finding shortest A data structure is described which can be used for paths 2, 13 and minimum cost spanning tree 2, 4, 25. representing a collection of priority queues. The Typical applications require primitive operations primitive operations are insertion, deletion, union, among the following five: INSERT, DELETE, MIN, UP update, and search for an item of earliest priority. DATE, and UNION. The operation INSERT (name, label, Key Words and Phrases: data structures, Q) adds an element to queue Q, while DELETE (name) implementation of set operations, priority queues, removes the element having that name. Operation MIN mergeable heaps, binary trees (Q) returns the name of the element in Q having the least CR Categories: 4.34, 5.24, 5.25, 5.32, 8.1 label, and UPDATE (name, label) changes the label of the element named. Finally, UNION (Q1, Q2, Q3) merges into I. Introduction Qa all elements of Q1 and Q2; the sets Q1 and Q2 become empty. In what follows, we assume that names are handled in a separate dictionary 2, 17 such as a hash In order to design correct and efficient algorithms for table or a balanced tree. If deletions are restricted to solving a specific problem, it is often helpful to describe elements extracted by MIN, such an auxiliary symbol our first approach to a solution in a language close to table is not needed. 1 that in which the problem is formulated. One such The heap, a truly elegant data structure discovered language is that of set theory, augmented by primitive by J. W. Williams and R. W. Floyd, handles a sequence set manipulation operations. Once the algorithm is out of n primitives INSERT, DELETE, and MIN, and runs in lined in terms of these set operations, one can then look O(nlogn) elementary operations using absolutely mini for data structures most suitable for representing each of 31 mal storage 17. For applications in which UNION is the sets involved. This choice depends only upon the necessary, more sophisticated data structures have been collection of primitive operations required for each set. devised, such as 23 trees 2, 17, leftist trees 5, 17, and It is thus important to establish a good catalogue of such binary heaps 9. data structures. A summary of the state of the art on this The data structure we present here handles an arbi question can be found in 2. In this paper, we add to trary sequence of n primitives, each drawn from the five this catalogue a data structure which allows efficient described above, in O(nlogn) machine operations and manipulation of priority queues. O(n) memory cells. It also allows for an efficient treat ment of a large number of updates, which is crucial in connection with spanning tree algorithms: Our data structure provides an implementation (described in 25) of the CheritonTarjanYao 3 minimum cost span General permission to make fair use in teaching or research of all ning tree algorithm which is much more straightforward or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice is given than the original one. and that reference is made to the publication, to its date of issue, and The proposed data structure uses less storage than to the fact that reprinting privileges were granted by permission of the leftist, AVL, or 23 trees; in addition, when the primitive Association for Computing Machinery. To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific operations are carefully machine coded from the pro permission as does republication, or systematic or multiple reproduc grams given in Section 4, they yield worst case running tion. times which compare favorably with those of their corn Author's address: Laboratoire de Recherche en Informatique, Brit. 490, Universit6 de ParisSud, Centre d'Orsay 91405Orsay, France. Weg'gsume here that indexing through the symbol table is done © 1978 ACM 00010782/78/04000309 00.75 in constant time. 309 Communications April 1978 of Volume 21 the ACM Number 4 Binomial tree Def. A binomial tree of order k is defined recursively: Order 0: single node. Order k: one binomial tree of order k – 1 linked to another of order k – 1. B B 0 k B k1 B k1 B B B B B 0 1 2 3 4 32Binomial tree properties Properties. Given an order k binomial tree B , k Its height is k. k It has 2 nodes. " k It has nodes at depth i. i The degree of its root is k. Deleting its root yields k binomial trees B , …, B . k–1 0 Pf. by induction on k B k+1 B B 0 1 B 2 B k B 4 33Binomial heap Def. A binomial heap is a sequence of binomial trees such that: Each tree is heapordered. There is either 0 or 1 binomial tree of order k. 6 3 18 37 8 29 10 44 30 23 22 48 31 17 45 32 24 50 55 B B B 4 1 0 34right Binomial heap representation Binomial trees. Represent trees using leftchild, rightsibling pointers. Roots of trees. Connect with singlylinked list, with degrees decreasing from left to right. root 6 3 18 6 3 18 37 29 10 37 29 44 48 31 17 48 10 50 50 31 17 44 binomial heap leftist powerof2 heap representation 35 parent leftBinomial heap properties Properties. Given a binomial heap with n nodes: The node containing the min element is a root of B , B , …, or B . 0 1 k It contains the binomial tree B iff b = 1, where b ⋅ b b b is binary i i k 2 1 0 representation of n. It has ≤ ⎣log n⎦ + 1 binomial trees. 2 Its height ≤ ⎣log n⎦. 2 6 3 18 37 8 29 10 44 n = 19 trees = 3 height = 4 30 23 22 48 31 17 binary = 10011 45 32 24 50 55 B B B 4 1 0 36Binomial heap: meld Meld operation. Given two binomial heaps H and H , (destructively) 1 2 replace with a binomial heap H that is the union of the two. Warmup. Easy if H and H are both binomial trees of order k. 1 2 Connect roots of H and H . 1 2 Choose node with smaller key to be root of H. 6 8 29 10 44 30 23 22 48 31 17 45 32 24 50 55 H H 2 1 37Binomial Heap: Meld 6 3 18 8 29 10 37 44 30 23 22 48 31 17 15 7 12 45 32 24 50 25 28 33 55 + 41 3812 Binomial Heap: Meld 18 6 3 18 8 29 10 37 44 30 23 22 48 31 17 15 7 12 45 32 24 50 25 28 33 55 + 41 393 12 18 7 37 25 6 3 18 8 29 10 37 44 30 23 22 48 31 17 15 7 12 45 32 24 50 25 28 33 55 + 41 12 18 403 3 12 18 15 7 37 7 37 28 33 25 25 41 6 3 18 8 29 10 37 44 30 23 22 48 31 17 15 7 12 45 32 24 50 25 28 33 55 + 41 12 18 413 3 12 18 15 7 37 7 37 28 33 25 25 41 6 3 18 8 29 10 37 44 30 23 22 48 31 17 15 7 12 45 32 24 50 25 28 33 55 + 41 3 12 15 7 37 18 28 33 25 41 423 3 12 18 15 7 37 7 37 28 33 25 25 41 6 3 18 8 29 10 37 44 30 23 22 48 31 17 15 7 12 45 32 24 50 25 28 33 55 + 41 6 3 12 8 29 10 44 15 7 37 18 30 23 22 48 31 17 28 33 25 45 32 24 50 41 43 55Binomial Heap: Meld 6 3 18 8 29 10 37 44 30 23 22 48 31 17 15 7 12 45 32 24 50 25 28 33 55 + 41 1 1 1 1 0 0 1 1 19 + 7 = 26 + 0 0 1 1 1 1 1 0 1 0 44Binomial heap: meld Meld operation. Given two binomial heaps H and H , (destructively) 1 2 replace with a binomial heap H that is the union of the two. Solution. Analogous to binary addition. Running time. O(log n). Pf. Proportional to number of trees in root lists ≤ 2 (⎣log n⎦ + 1). ▪ 2 1 1 1 1 0 0 1 1 19 + 7 = 26 + 0 0 1 1 1 1 1 0 1 0 45Binomial heap: extract the minimum Extractmin. Delete the node with minimum key in binomial heap H. Find root x with min key in root list of H, and delete. 6 18 3 8 29 10 44 37 30 23 22 48 31 17 H 45 32 24 50 55 46Binomial heap: extract the minimum Extractmin. Delete the node with minimum key in binomial heap H. Find root x with min key in root list of H, and delete. H' ← broken binomial trees. H ← MELD(H', H). Running time. O(log n). 6 18 8 29 10 44 37 30 23 22 48 31 17 H 45 32 24 50 H' 55 47Binomial heap: decrease key Decrease key. Given a handle to an element x in H, decrease its key to k. Suppose x is in binomial tree B . k Repeatedly exchange x with its parent until heap order is restored. Running time. O(log n). 3 6 18 8 29 10 44 37 30 23 22 48 31 17 H x 32 24 50 55 48Binomial heap: delete Delete. Given a handle to an element x in a binomial heap, delete it. DECREASEKEY(H, x, ∞). DELETEMIN(H). Running time. O(log n). 3 6 18 8 29 10 44 37 30 23 22 48 31 17 H 45 32 24 50 55 49Binomial heap: insert Insert. Given a binomial heap H, insert an element x. H' ← MAKEHEAP( ). H' ← INSERT(H', x). H ← MELD(H', H). Running time. O(log n). 3 6 18 x H' 8 29 10 44 37 30 23 22 48 31 17 H 32 45 24 50 55 50Binomial heap: sequence of insertions Insert. How much work to insert a new node x 3 6 x If n = .......0, then only 1 credit. If n = .......01, then only 2 credits. 29 10 37 44 If n = .......011, then only 3 credits. If n = .......0111, then only 4 credits. 48 31 17 50 Observation. Inserting one element can take Ω(log n) time. if n = 11...111 Theorem. Starting from an empty binomial heap, a sequence of n consecutive INSERT operations takes O(n) time. Pf. (n / 2) (1) + (n / 4)(2) + (n / 8)(3) + … ≤ 2 n. ▪ k i k 1 =2 i k k 1 2 2 2 i=1 2 51Binomial heap: amortized analysis Theorem. In a binomial heap, the amortized cost of INSERT is O(1) and the worstcase cost of EXTRACTMIN and DECREASEKEY is O(log n). Pf. Define potential function Φ(H ) = trees(H ) = trees in binomial heap H . i i i Φ(H ) = 0. 0 Φ(H ) ≥ 0 for each binomial heap H . i i Case 1. INSERT Actual cost c = number of trees merged + 1. i ∆Φ = Φ(H ) – Φ(H ) = 1 – number of trees merged. i i–1 Amortized cost = ĉ = c + Φ(H ) – Φ(H ) = 2. i i i i–1 52Binomial heap: amortized analysis Theorem. In a binomial heap, the amortized cost of INSERT is O(1) and the worstcase cost of EXTRACTMIN and DECREASEKEY is O(log n). Pf. Define potential function Φ(H ) = trees(H ) = trees in binomial heap H . i i i Φ(H ) = 0. 0 Φ(H ) ≥ 0 for each binomial heap H . i i Case 2. DECREASEKEY Actual cost c = O(log n). i ∆Φ = Φ(H ) – Φ(H ) = 0. i i–1 Amortized cost = ĉ = c = O(log n). i i 53Binomial heap: amortized analysis Theorem. In a binomial heap, the amortized cost of INSERT is O(1) and the worstcase cost of EXTRACTMIN and DECREASEKEY is O(log n). Pf. Define potential function Φ(H ) = trees(H ) = trees in binomial heap H . i i i Φ(H ) = 0. 0 Φ(H ) ≥ 0 for each binomial heap H . i i Case 3. EXTRACTMIN or DELETE Actual cost c = O(log n). i ∆Φ = Φ(H ) – Φ(H ) ≤ Φ(H ) ≤ ⎣log n⎦. i i–1 i 2 Amortized cost = ĉ = c + Φ(H ) – Φ(H ) = O(log n). ▪ i i i i–1 54Priority queues performance cost summary operation linked list binary heap binomial heap binomial 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(log n) DELETE O(1) O(log n) O(log n) O(log n) homework † MELD O(1) O(n) O(log n) O(1) FINDMIN O(n) O(1) O(log n) O(1) † amortized Hopeless challenge. O(1) INSERT, DECREASEKEY and EXTRACTMIN. Why Challenge. O(1) INSERT and DECREASEKEY, O(log n) EXTRACTMIN. 55
Website URL
Comment