CSE332: Data AbstractionsLecture 4: Priority QueuesTyler RobisonSummer 20101A new ADT: Priority Queue2 Textbook Chapter 6: Priority Queues Will go back to binary search trees (4) and hashtables (5) later A priority queue holds compare-able data Unlike stacks and queues need to compare items Given x and y, is x less than, equal to, or greater than y What this means can depend on your data Numbers: numeric ordering Strings: lexicon ordering Employee profile: lexicon ordering on name? Id? Much of course will require comparable items: Sorting Binary Search Trees Integers are comparable, so will use them in examples But the priority queue ADT is much more generalPriority Queues3 Assume each item has a “priority” The lesser value item is the one with the greater priority So “priority 1” is more important than “priority 4” (Just a convention) Operations:  insert deleteMin create, is_empty, destroy Key property: deleteMin returns and deletes from the queue the item with greatest priority (lowest priority value) Can resolve ties arbitrarilyinsertdeleteMin6 215 2312 1845 3 7Focusing on the numbers4 For simplicity in lecture, we‟ll often suppose items are just ints and the int is the priority So an operation sequence could beinsert 6insert 5x = deleteMin– int priorities are common, but really just need comparable Not having “other data” is very rare Example: print job is a priority and the fileExample5insert 5insert 3insert 4a = deleteMinb = deleteMininsert 2insert 6c = deleteMind = deleteMin Analogy: insert is like enqueue, deleteMin is like dequeue But the whole point is to use priorities instead of FIFO3425Applications6Like all good ADTs, the priority queue arises often Run multiple programs in the operating system “critical” before “interactive” before “compute-intensive” Maybe let users set priority level Treat hospital patients in order of severity (or triage) Select print jobs in order of decreasing length? Forward network packets in order of urgency Select most frequent symbols for data compression (cf. CSE143) Sort: insert all, then repeatedly deleteMin Much like Project 1 uses a stack to implement reverseMore applications for Priority Queues7 “Greedy” algorithms Perform the „best-looking‟ choice at the moment Will see an example when we study graphs in a few weeks Discrete event simulation (system modeling, virtual worlds, …) Simulate how state changes when events fire Each event e happens at some time t and generates new events e1, …, en at times t+t1, …, t+tn Naïve approach: advance “clock” by 1 unit at a time and process any events that happen then Better: Pending events in a priority queue (priority = time happens) Repeatedly: deleteMin and then insert new events Effectively, “set clock ahead to next event”Need a good data structure!8 Will show an efficient, non-obvious data structure for this ADT But first let‟s analyze some “obvious” ideas for n data items All times worst-case; but assume arrays “have room”data insert algorithm / time deleteMin algorithm / timeunsorted arrayunsorted linked listsorted circular arraysorted linked listbinary search treeadd at end O(1) search O(n)add at front O(1) search O(n)search / shift O(n) move front O(1)put in right place O(n) remove at front O(1)put in right place O(n) leftmost O(n)More on possibilities9 If priorities are random, binary search tree will likely do better O(log n) insert and O(log n) deleteMin on average One more idea: if priorities are 0, 1, …, k can use array of lists insert: add to front of list at arr[priority], O(1) deleteMin: remove from lowest non-empty list O(k) Only really feasible for small k But we are about to see a data structure called a “binary heap” O(log n) insert and O(log n) deleteMin worst-case Very good constant factors If items arrive in random order, then insert is O(1) on average!Tree terms (review?)10The binary heap data structure implementing the priority queue ADT will be a tree, so worth establishing some terminologyAEBD FCGIHLJ MK NTree Troot(tree)children(node)parent(node)leaves(tree)siblings(node)ancestors(node)descendents(node)subtree(node)depth(node)height(tree)degree(node)branching factor(tree)Kinds of trees11Certain terms define trees with specific structure Binary tree: Each node has at most 2 children n-ary tree: Each node as at most n children Complete tree: Each row is completely full except maybe the bottom row, which is filled from left to rightLater we‟ll learn a tree is a kind of directed graph with specific structureBinary Heap: Priority Queue DS12Finally, then, a binary min-heap (aka binary heap or just heap) has the following 2 properties: Structure property : A complete tree Heap ordering property: For every (non-root) node the parent node‟s value is less than the node‟s value153080201099604080201050 70085not a heapa heapSo:• Where is the highest-priority item?• What is the height of a heap with n items?rootO(logn)Operations: basic idea13 findMin: return root.data deleteMin: 1. answer = root.data2. Move right-most node in last row to root to restore structure property3. “Percolate down” to restore heap property insert:1. Put new node in next position on bottom row to restore structure property2. “Percolate up” to restore heap property99604080201050 70085DeleteMin141. Delete (and return) value at root node3498571069112. Restore the Structure Property15 We now have a “hole” at the root Need to fill the hole with another value When we are done, the tree will have one less node and must still be complete3498571069113498571069113. Restore the Heap Property16Percolate down: • Keep comparing with both children • Move smaller child up and go down one level• Done if both children are  item or reached a leaf node• What is the run time?•Why not swap with larger of children, if it‟s smaller than both?349857106911?849105769113498576911310?O(logn)Insert17 Add a value to the tree Structure and heap order properties must still be correct afterwards8491057691112Insert: Maintain the Structure Property18 There is only one valid tree shape after we add one more node So put our new