P Q RIORITY UEUES ‣ binary heaps ‣ d-ary heaps ‣ binomial heaps ‣ Fibonacci heaps Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley http://www.cs.princeton.edu/~wayne/kleinberg-tardos Last updated on Apr 10, 2013 5:50 AM Priority 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. ・ UNION(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. 2 Priority 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 3 P Q RIORITY UEUES ‣ binary heaps ‣ d-ary heaps ‣ binomial heaps Algorithms ‣ Fibonacci heaps F O U R T H E D I T I O N R S | K W OBERT EDGEWICK EVIN AYNE SECTION 2.4 Complete 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. ▪ 5 A complete binary tree in nature 6 Binary heap Binary heap. Heap-ordered complete binary tree. Heap-ordered. For each child, the key in child ≤ key in parent. 6 parent 10 8 child 12 18 child 11 25 21 17 19 7 Explicit 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 8 Implicit 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 9 Binary heap demo heap ordered 6 10 8 12 18 11 25 21 17 19 10