Slide 1A new ADT: Priority QueuePrioritiesFocusing on the numbersExampleApplicationsMore applicationsNeed a good data structure!Need a good data structure!More on possibilitiesTree terms (review?)Kinds of treesOur data structureOperations: basic ideaDeleteMin2. Restore the Structure Property3. Restore the Heap PropertyDeleteMin: Run Time AnalysisInsertInsert: Maintain the Structure PropertyMaintain the heap propertyInsert: Run Time AnalysisCSE332: Data AbstractionsLecture 4: Priority QueuesDan GrossmanSpring 2010A new ADT: Priority Queue•Textbook Chapter 6–Will go back to binary search trees–Nice to see a new and surprising data structure first•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–Much of course will require this: dictionaries, sorting–Integers are comparable, so will use them in examples•But the priority queue ADT is much more generalSpring 2010 2CSE332: Data AbstractionsPriorities•Assume each item has a “priority”–The lesser 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 arbitrarilySpring 2010 3CSE332: Data AbstractionsinsertdeleteMin 6 2 15 23 12 1845 3 7Focusing on the numbers•For simplicity in lecture, we’ll often suppose items are just ints and the int is the priority–The same concepts without generic usefulness–So an operation sequence could beinsert 6 insert 5 x = 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 fileSpring 2010 4CSE332: Data AbstractionsExampleinsert x1 with priority 5insert x2 with priority 3insert x3 with priority 4a = deleteMinb = deleteMininsert x4 with priority 2insert x5 with priority 6c = deleteMind = deleteMin •Analogy: insert is like enqueue, deleteMin is like dequeue–But the whole point is to use priorities instead of FIFOSpring 2010 5CSE332: Data AbstractionsApplicationsLike all good ADTs, the priority queue arises often–Sometimes “directly”, sometimes less obvious•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 reverseSpring 2010 6CSE332: Data AbstractionsMore applications•“Greedy” algorithms–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”Spring 2010 7CSE332: Data AbstractionsNeed a good data structure!•Will show an efficient, non-obvious data structure for this ADT–But first let’s analyze some “obvious” ideas–All times worst-case; assume arrays “have room”data insert algorithm / time deleteMin algorithm / timeunsorted array unsorted linked listsorted circular arraysorted linked listbinary search treeSpring 2010 8CSE332: Data AbstractionsNeed a good data structure!•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; assume arrays “have room”data insert algorithm / time deleteMin algorithm / timeunsorted array add at end O(1) search O(n)unsorted linked list add at front O(1) search O(n)sorted circular array search / shift O(n) move front O(1)sorted linked list remove at front O(1) put in right place O(n)binary search tree put in right place O(n)leftmost O(n)Spring 2010 9CSE332: Data AbstractionsMore on possibilities•If priorities are random, binary search tree will likely do better–O(log n) insert and O(log n) deleteMin on average•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•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)Spring 2010 10CSE332: Data AbstractionsTree terms (review?)The binary heap data structure implementing the priority queue ADT will be a tree, so worth establishing some terminologySpring 2010 11CSE332: Data AbstractionsAEBD 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 treesCertain 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 rightSpring 2010 12CSE332: Data AbstractionsTeaser: Later we’ll learn a tree is a kind of directed graph with specific structureOur data structureFinally, then, a binary min-heap (or just binary heap or just heap) is:•A complete tree – the “structure property”•For every (non-root) node the parent node’s value is less than the node’s value – the “heap property” (not a binary search tree)Spring 2010 13CSE332: Data Abstractions153080201099604080201050 70085not a heapa heapSo:•Where is the highest-priority item?•What is the height of a heap with n items?Operations: basic idea•findMin: return root.data•deleteMin: