Question? Leave a message!




Priority queue data type

Priority queue data type
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Website URL
Comment
PRIORITY QUEUES binary heaps ‣ d-ary heaps ‣ binomial heaps ‣ Fibonacci heaps ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Sep 8, 2013 7:00 AMPriority queue data type A min-oriented priority queue supports the following core operations: MAKE-HEAP(): create an empty heap. INSERT(H, x): insert an element x into the heap. EXTRACT-MIN(H): remove and return an element with the smallest key. DECREASE-KEY(H, x, k): decrease the key of element x to k. The following operations are also useful: IS-EMPTY(H): is the heap empty? FIND-MIN(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 totally-ordered universe. 2Priority queue applications Applications. A search. Heapsort. Online median. Huffman encoding. Prim's MST algorithm. Discrete event-driven simulation. Network bandwidth management. Dijkstra's shortest-paths algorithm. … http://younginc.site11.com/source/5895/fos0092.html 3PRIORITY QUEUES binary heaps ‣ d-ary 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. Heap-ordered complete binary tree. Heap-ordered 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, EXTRACT-MIN, and DECREASE-KEY 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, DECREASE-KEY, and EXTRACT-MIN take O(log n) time in the worst case. 14Binary heap: find-min 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. Bottom-up method. For i = n to 1, repeatedly exchange the element in node i with its smaller child until subtree rooted at i is heap-ordered. 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 MAKE-HEAP O(1) O(1) ISEMPTY O(1) O(1) INSERT O(1) O(log n) EXTRACT-MIN O(n) O(log n) DECREASE-KEY O(1) O(log n) DELETE O(1) O(log n) MELD O(1) O(n) FIND-MIN O(n) O(1) 20