Home PageTitle PageContentsJJ IIJ IPage 1 of 18Go BackFull ScreenCloseQuitIntroduction to Priority Queues• Want to maintain a collection of n items to support findMin,insert and deleteMin in O(log n) time– Note that we are not interested in doing arbitrary remove() orfind()– A linked list or array requires that some operations take O(n)time– An unbalanced binary search tree does not have a good worstcase. A balanced tree (or even splay trees) is too much work• A binary heap is implemented like an array and in addition supportsinsert in O(1) expected time, and findMin in worst-case O(1)time.• Excellent for general hierarchical searches, and possibly sortingHome PageTitle PageContentsJJ IIJ IPage 2 of 18Go BackFull ScreenCloseQuitWhat Is A Heap?• A heap is a complete binary tree that stores keys in internal nodeswith the order property key(parent) ≤ key(child)• Height of the tree is logarithmic• With n keys, a heap can be constructed in O(n) time (stored in anarray of size n)Home PageTitle PageContentsJJ IIJ IPage 3 of 18Go BackFull ScreenCloseQuitInsertion Into Heap: Percolate Up• Create a hole in the next available location. If key can be placed inthe hole, done.• Otherwise, percolate the key into its parent and recurse (till root)• Efficient algorithm by placing −∞ at position 0 of the heap to avoidtesting of rootHome PageTitle PageContentsJJ IIJ IPage 4 of 18Go BackFull ScreenCloseQuitExampleHome PageTitle PageContentsJJ IIJ IPage 5 of 18Go BackFull ScreenCloseQuitExampleHome PageTitle PageContentsJJ IIJ IPage 6 of 18Go BackFull ScreenCloseQuitRemove Minimimum From Heap: Percolate Down• Key at root is removed creating a hole• Conceptually move last key in array to root• Percolate down so that order property is satisfiedHome PageTitle PageContentsJJ IIJ IPage 7 of 18Go BackFull ScreenCloseQuitExampleHome PageTitle PageContentsJJ IIJ IPage 8 of 18Go BackFull ScreenCloseQuitExampleHome PageTitle PageContentsJJ IIJ IPage 9 of 18Go BackFull ScreenCloseQuitExampleHome PageTitle PageContentsJJ IIJ IPage 10 of 18Go BackFull ScreenCloseQuitApplication of Heaps: Nearest Neighbor• Given hierarchical data structure containing points (in general dataobjects) and a query object• We want to output the data object closest to the query object• Approach: Recursive travel of the data structure using a priorityqueue to prune the search space– Q contains objects with a lower bound– Want to insert and remove items from Q– We stop searching if current cost is less than the lower boundstored in QHome PageTitle PageContentsJJ IIJ IPage 11 of 18Go BackFull ScreenCloseQuitNearest Neighbor: Pruned versionf l o a t lowerbound ( Rectangle r , Point p ) {i f ( r . i n s i d e ( p ) ) return 0 ;i f ( r . l e f t (p ) ) return r . minX − p . x ;i f ( r . r i g h t (p ) ) return p . x − r .maxX ;i f ( r . southEastCorner ( p ) ) . . .}Result p r o c e s s (KDNode k , int cd , Rec tangle r , R es ul t r e s ) {i f ( k == n u l l ) return r e s ;i f ( lowerbound ( r , q) >= r e s . d i s t a n c e ) return r e s ;f l o a t d i s t = d i s t a n c e ( node . data , query ) ;i f ( d i s t < r e s . d is t a n c e ) {r e s u l t . p oin t = node . data ;r e s u l t . di s t a n c e = d i s t a n c e ( node . data , query ) ;}i f ( q [ cd ] < k . data [ cd ] ) . . . e l s e . . .return r e s ;}Home PageTitle PageContentsJJ IIJ IPage 12 of 18Go BackFull ScreenCloseQuitNearest Neighbor: Pruned versionResult p r o c e s s (KDNode k , int cd , Rec tangle r , R es ul t r e s ) {f l o a t d i s t = d i s t a n c e ( node . data , query ) ;i f ( d i s t < r e s . d is t a n c e ) {r e s u l t . p oin t = node . data ;r e s u l t . di s t a n c e = d i s t a n c e ( node . data , query ) ;}i f ( q [ cd ] < k . data [ cd ] ) {r e s = p r o c e s s ( k . l e f t , cd +1, r . tri m L e f t ( cd , k . data ) , r e s ) ;r e s = p r o c e s s ( k . r i g h t , cd +1, r . trimRight ( cd , k . data ) , r e s ) ;}e l s e {r e s = p r o c e s s ( k . r i g h t , cd +1, r . trimRight ( cd , k . data ) , r e s ) ;r e s = p r o c e s s ( k . l e f t , cd +1, r . tri m L e f t ( cd , k . data ) , r e s ) ;}return r e s ;}Home PageTitle PageContentsJJ IIJ IPage 13 of 18Go BackFull ScreenCloseQuitWhich Nodes Are Processed?Home PageTitle PageContentsJJ IIJ IPage 14 of 18Go BackFull ScreenCloseQuitAny Improvement Possible?• Nine nodes examined. Can we do better?• Yes, if decision to pick a node is based on dynamic changing costsinstead of initial left-right decision.• Use a priority queue. (Seven nodes examined instead of nine)Home PageTitle PageContentsJJ IIJ IPage 15 of 18Go BackFull ScreenCloseQuitGeneral Structure Of Algorithm• Elements in Q are pairs (node, lowerbound)• Initialize:– Insert (root,0) into Q– Nearest object = NULL, and distance = ∞• Body of the algorithm: While Q is not empty and findmin(Q).cost< result.distance1. Node = deleteMin(Q);2. If (isInternal(node)) insertQ(child, lowerbound(child)3. Otherwise, process(node)Home PageTitle PageContentsJJ IIJ IPage 16 of 18Go BackFull ScreenCloseQuitNearest Neighbor: Priority Q VersionQ contents• [(35, 90), 0]; !• [(70, 80), 0],[(10, 75), 5];• [(80, 40), 0],[(10, 75), 5],[(50, 90), 30];• [(70, 30), 0], . . . ,[(90, 60), 40]; !• [(10, 75), 5],[(50, 25, 20], . . . ;• [(25, 10), 5], . . . ,• [(20, 50), 15], . . . , !Home PageTitle PageContentsJJ IIJ IPage 17 of 18Go BackFull ScreenCloseQuitNearest Neighbor: Q versionin s e r tQ (KDNode n , f l o a t c o s t , int cd ) {// i n s e r t i n to a p r i o r t y Q based on c o s t .// s t o r e cu t t …