Priority Queues - Ed. 2. and 3.: Chapter 7 - Ed. 4.: Chapter 8 - Priority Queues (Chapter 7) Priority Queue ADT - Keys, Priorities, and Total order Relations - Sorting with a Priority Queue Priority Queue implementation - Implementation with an unsorted sequence - Implementation with a sorted sequence The Priority Queue Abstract Data Type Suppose that you have a few assignments from different

courses. Which assignment will you want to work on first? Course Database Systems UNIX Data Structure & Algorithm Structured Systems Analysis Priority 2 4 1 3 Due day October 3 October 10

September 29 October 7 You set your priority based on due days. Due days are called keys. When you want to determine the priority for your assignments, you need a value for each assignment, that you can compare with each other. key: An object that is assigned to an element as a specific attribute for that element, which can be used to identify, rank, or weight that element. Example: Student records Student Name Bill Scott

Bob Jones Alan Smith Susan Kane Student Number 110102 110140 110243 110176 Final Score 65 76 86 80

Any of the attributes, Student Name, Student Number, or Final Score can be used as keys. Note: Keys may not be unique (Final Score). Example: Brand Motormaster Goodyear Michelin Price $61.49 $98.99 $101.99 Warranty (km)

110,000 220,000 150,000 Suppose we are looking for tires for a passenger car. How can we weight the tires so we can select the tires? The key may consist of not only one attribute such as price. In fact, we want to consider factors such as brands and warranty as well. So the key may be more complex than just one value. We want a comparison rule that will never contradict itself. This requires that the rule define a total order relation. total order relation: Reflexive property: k k. Antisymmetric property: if k1 k2 and k2 k1 , then k1 = k2.

Transitive property: if k1 k2 and k2 k3 , then k1 k3. Examples: Integers, real numbers, lexicographic order of character sequence. Not everything can have a total order relation. Non-example: For 2-D vectors v1 = (x1, x2) and v2 = (x3, x4), define the following ordering rule: v1 v2 if x2 - x1 = = x4 - x3 Then we have 4-1=7-4 Therefore, (1, 4) (4, 7) and (4, 7) (1, 4). But (1,4) (7, 4), namely, the relation does not satisfy the antisymmetric property.

If a comparison rule defines a total order relation, it will never lead to a comparison contradiction. the smallest key: If we have a finite number of elements with a total order relation, then the smallest key, denoted by kmin, is well-defined: kmin is the key that satisfies kmin k for any other key k. Being able to find the smallest key is very important because in many cases, we want to have the element with the smallest key. priority queue: A container of elements, each having an associated key that is provided at the time the element is inserted. The two fundamental methods of a priority queue P: insertItem(k,e): Insert an element e with key k into P. removeMin(): Return and remove from P an element with the smallest key.

Example 7.1 The airline company keeps a priority queue of standby passengers waiting to get a seat. passenger 1 passenger 2 passenger 3 passenger 4 Fare Paid Frequent-Flyer Status (0 - 6 stars) $216 2 $198 6

$315 4 $267 5 Days of Standby 15 20 7 10 The keys consist of three attributes: Fare paid, frequent-flyer status, and days of standby. Sorting with a Priority Queue

Recall that a priority queue has the method removeMin() to remove and return the element with the smallest key. This fact makes priority queues useful for sorting. Assume we have a sequence S of n elements The application has two steps: 1.Put the elements of S into an initially empty priority queue P by calling the method insertItem() n times. 2.Extract elements from P by calling the method removeMin() n times, and put them back into S in order. Algorithm PriorityQueueSort( S, P ) for each element in S get an element from S and assign it to variable e call P.insertItem( e, e ) while P is not empty call P.removeMin() to get an element from P

insert the element to S Note that the keys are the elements themselves. E x a m p le : W e h a v e a s e q u e n c e S w ith 6 in te g e rs (e le m e n ts ). A ls o w e h a v e a n e m p ty p rio rity q u e u e P . S 4 P 0 7 8

2 1 A fte r th e firs t s te p , a ll th e e le m e n ts a re n o w in th e p rio rity q u e u e , w ith th e m s e lv e s a s k e y s . S P 0 ,0 1 ,1 2 ,2 4 ,4

7 ,7 8 ,8 T h e firs t th re e e le m e n ts h a v e b e e n e x tra c te d fro m P a n d in s e rte d in to S in o rd e r. T h e e le m e n t w ith th e s m a lle s t k e y in P n o w is 4 ,4 , w h ic h w ill b e e x tr a c te d n e x t tim e . S 0 1 2 P

4 ,4 7 ,7 8 ,8 A fte r th e s e c o n d s te p : N o w th e e le m e n ts a re s o rte d in S . S 0 P 1 2 4

7 8 Methods of a Priority Queue The priority queue abstract data type supports the following methos: size(): Return the number of elements in P. Input: None; Output: Integer isEmpty(): Test whether P is empty. Input: None; Output: Boolean inserItem(k,e): Insert a new element e with key k into P. Input: Objects k (key) and e (element); Output: None minElement(): Return (but do not remove) an element of P with the smallest key; an error condition occurs if the priority queue

is empty. Input: None; Output: Object (element) minKey(): Return a smallest key in P; an error condition occurs if the priority queue is empty. Input: None; Output: Object (key) removeMin(): Remove from P and return an element with the smallest key; an error condition occurs if the priority queue is empty. Input: None; Output: Object (element) Example 7.2: The following table shows a series of operations and their effects on an initially empty priority queue P. Operation insertItem(5,A) insertItem(9,C)

insertItem(3,B) insertItem(7,D) minElement() minKey() removeMin() size() removeMin() removeMin() removeMin() removeMin() isEmpty() Output B 3 B

3 A D C error true Priority Queue {(5,A)} {(5,A),(9,C)} {(3,B),(5,A),(9,C)} {(3,B),(5,A),(7,D),(9,C)} {(3,B),(5,A),(7,D),(9,C)} {(3,B),(5,A),(7,D),(9,C)} {(5,A),(7,D),(9,C)} {(5,A),(7,D),(9,C)}

{(7,D),(9,C)} {(9,C)} {} {} {} Items in a Priority Queue Recall that when we insert an element into a priority queue, we need to assign a key to the element. Later, when we need to extract the element from the priority queue, we need to suppy the key. Therefore, items stored in the priority queue are pairs. Here is a Java implementation of the pairs as class Item. public class Item { private Object key, elem; protected Item( Object k, Object e ) {

key = k; elem = e; } public Object key() { return key; } public Object element() { return elem; } public void setKey( Object k ) { key = k; } public void setElement( Object e ) { elem = e; } } The Comparator Abstract Data Type Recall that the priority queue method removeMin() returns the element with the smallest key. To find the element with the smallest key, keys of elements in a priority queue have to be compared. This can be handled by objects called comparators. The comparator abstract data type supports the following

methods: isLessThan(a,b) True if and only if a is less than b. Input: Pair of objects; Output: Boolean isLessThanOrEqualTo(a,b): True if and only if a is less than or equal to b. Input: Pair of objects; Output: Boolean isEqualTo(a,b): True if and only if a and b are equal. Input: Pair of objects; Output: Boolean isGreaterThan(a,b): True if and only if a is greater than b. Input: Pair of objects; Output: Boolean isGreaterThanOrEqualTo(a,b): True if and only if a is greater than or equal to b. Input: Pair of objects; Output: Boolean isComparable(a): True if and only if a can be compared. Input: Object; Output: Boolean Class Lexicographic

As an application of the comparator ADT, here is a Java class Lexicographic for comparison of 2-D points. public class Lexicographic implements Comparator { int xa, ya, xb, yb; // Assume objects are class Point2D objects private void getXY( Object a, Object b ) { if( a == null || b == null ) throw new InvalidElementException( "Null Argument" ); try { xa = (( Point2D )a ).getX(); ya = (( Point2D )a ).getY(); xb = (( Point2D )b ).getX(); yb = (( Point2D )b ).getY(); }

catch( ClassCastException e ) { throw new InvalidElementException( "Argument not a Point2D" ); } } public boolean isLessThan( Object a, Object b ) { getXY( a, b ); if( xa == xb ) return( ya < yb ); else return( xa < xb ); } Examples: Object a

(1, 3) (7, 1) (4, 5) Object b (1, 4) (5, 2) (5, 2 ) return value true false true public boolean isLessThanOrEqualTo( Object a, Object b ) { getXY( a, b );

if( xa == xb ) return( ya <= yb ); else return( xa <= xb ); } Examples: Object a (2, 3) (7, 1) (4, 5) Object b (2, 3) (5, 2) (5, 2 )

return value true false true public boolean isEqualTo( Object a, Object b ) { getXY( a, b ); return ( xa == xb ) && ( ya == yb ); } Examples: Object a (2, 3) (7, 1) (4, 5)

Object b (2, 3) (5, 2) (5, 2 ) return value true false false public boolean isComparable( Object a ) { if( a == null ) return a; else { try { Point2D p = ( Point2D )a; }

catch( ClassCastException e ) { return false; } return true; } } The function returns false if object a is null or it is not a Poin2D type. Data Structure Exercises 14.1 Implementing a Priority Queue with a Sequence Suppose that we want to write a program that using a priority queue to help us select tires. How can we implement a priority queue? Brand

Motormaster Goodyear Michelin Price $61.49 $98.99 $101.99 Warranty (km) 110,000 220,000 150,000 Recall that both a sequence and a priority queue are containers of some elements. Therefore, we can use a sequence to

implement a priority queue. The elements in the sequence are the pairs of keys and elements. There are two ways to implement a priority queue with a sequence: 1.Keys in the sequence are sorted. 2.Keys in the sequence are not sorted. Implementation with an Unsorted Sequence Let S be a sequence. A pair of key and element is denoted as p=(k,e). With an unsorted sequence, we use the method insertLast(p) of S to implement insertItem(k,e) of the priority queue P. To perform operations including minElement, minKey, and removeMin, we have to inspect all the elements of the sequence S to find the element with the smallest key.

E x a m p le : A s s u m e w e h a v e th e e le m e n ts s to re d in a n u n s o rte d s e q u e n c e sh o w h e re . T o p e rfo rm th e re m o v e M in () o p e ra tio n , w e h a v e to in s p e c t a ll e le m e n ts to f in d th e e le m e n t ( 0 ,0 ) th a t h a s th e s m a lle s t k e y . P 1 ,1 4 ,4 0 ,0 2 ,2 7 ,7

8 ,8 Implementation with an Sorted Sequence Let S be a sequence. A pair of key and element is denoted as p=(k,e). With an sorted sequence, we can easily extract the element with the smallest key with the combination of methods remove() and first() of S. However, to perform operation insertItem, we need to scan through the sequence S to find the apropriate position to insert the new element and key. E x a m p le : T o in s e rt th e p a ir (6 ,6 ), w e h a v e to s c a n th ro u g h th e s e q u e n c e u n til w e f in d th e r ig h t p la c e ( b e tw e e n ( 4 ,4 ) a n d ( 7 ,7 ) ) . P 0 ,0

1 ,1 2 ,2 4 ,4 7 ,7 6 ,6 8 ,8 Comparing the Two Implementations Assume that the size of the sequence is n. Method size, isEmpty

insertItem minElement, minKey, removeMin Unsorted S fast fast O(n) Sorted S fast O(n) fast Class SortedSequencePriorityQueue public class SortedSequencePriorityQueue implements PriorityQueue {

protected Sequence S = new NodeSequence(); protected Comparator comp; protected Object key( Position pos ) { return (( Item )pos.element()).key(); } protected Object elem( Position pos ) { return (( Item )pos.element()).element(); } protected Object elem( Object kep ) { return (( Item )kep ).element() } public SortedSequencePriorityQueue( Comparator c ) { comp = c; } public int size() { return S.size(); } public boolean isEmpty() { return S.isEmpty() }

public void insertItem( Object k, Object e ) throws InvalidKeyException { if( !comp.isComparable( k )) throws new InvalidKeyException( "The key is not valid" ); else if( S.isEmpty()) S.insertFirst( new Item( k, e )); else if( comp.isGreaterThan( k,key(S.last()))) S.insertAfter( S.last(), new Item( k, e )); else { Position curr = S.first(); while( comp.isGreaterThan( k, key( curr ))) curr = S.after( curr ); S.insertBefore( curr, new Item( k, e )); }

} curr P 0,0 1,1 2,2 4 ,4 7 ,7 6 ,6 k = 6, e = 6

8 ,8 public Object removeMin() throws PriorityQueueEmptyException { if( S.isEmpty()) throw new PriorityQueueEmptyException( "The priority queue is empty" ); else return elem( S.remove( S.first())); } Selection Sort and Insertion Sort Recall that we can use a priority queue to sort elements. Depending on whether a sorted sequence is used to implement the priority queue, we have two kinds of sort. If the priority queue is implemented with an unsorted sequence,

it is called selection-sort. The table here shows the performance of selection sort on sequence (7, 4, 8, 2, 5, 3, 9). Input Phase 1 Phase 2 Sequence S (7, 4, 8, 2, 5, 3, 9) (4, 8, 2, 5, 3, 9) (8, 2, 5, 3, 9) () (2)

(2, 3) (2, 3, 4) (2, 3, 4, 5) (2, 3, 4, 5, 7) (2, 3, 4, 5, 7, 8) (2, 3, 4, 5, 7, 8, 9) Priority Queue P () (7) (7, 4) (7, 4, 8, 2, 5, 3, 9) (7, 4, 8, 5, 3, 9) (7, 4, 8, 5, 9) (7, 8, 5, 9)

(7, 8, 9) (8, 9) (9) () If the priority queue is implemented with a sorted sequence, the sort is called insertion sort. The table here shows the performance of insertion sort on the same sequence S = (7, 4, 8, 2, 5, 3, 9). Input Phase 1 Phase 2 Sequence S (7, 4, 8, 2, 5, 3, 9)

(4, 8, 2, 5, 3, 9) (8, 2, 5, 3, 9) (2, 5, 3, 9) (5, 3, 9) (3, 9) (9) () (2) (2, 3) (2, 3, 4, 5, 7, 8, 9) Priority Queue P () (7) (4, 7)

(4, 7, 8) (2, 4, 7, 8) (2, 4, 5, 7, 8) (2, 3, 4, 5, 7, 8) (2, 3, 4, 5, 7, 8, 9) (7, 4, 8, 5, 3, 9) (7, 4, 8, 5, 9) () The table here is a comparison of running time for both kinds of sort. Selection Sort Insertion Sort Phase 1 O(n) O(n2)

O(n) Phase 2 O(n2) Overall O(n2) O(n2) Recall that the runnint time for bobble sort is also propotional to the size of the square of n, the size of the sequence. Data Structure Exercises 15.1 Implementing a Priority Queue with a Sequence Suppose that we want to write a program that using a priority queue to help us select tires. How can we implement a priority

queue? Brand Motormaster Goodyear Michelin Price $61.49 $98.99 $101.99 Warranty (km) 110,000 220,000 150,000

Recall that both a sequence and a priority queue are containers of some elements. Therefore, we can use a sequence to implement a priority queue. The elements in the sequence are the pairs of keys and elements. There are two ways to implement a priority queue with a sequence: 1. Keys in the sequence are sorted. 2. Keys in the sequence are not sorted. Implementation with an Unsorted Sequence Let S be a sequence. A pair of key and element is denoted as p=(k,e). With an unsorted sequence, we use the method insertLast(p) of S to implement insertItem(k,e) of the priority queue P. To perform operations including minElement, minKey, and removeMin, we have to inspect all the elements of the

sequence S to find the element with the smallest key. E x a m p le : A s s u m e w e h a v e th e e le m e n ts s to re d in a n u n s o rte d s e q u e n c e sh o w h e re . T o p e rfo rm th e re m o v e M in () o p e ra tio n , w e h a v e to in s p e c t a ll e le m e n ts to f in d th e e le m e n t ( 0 ,0 ) th a t h a s th e s m a lle s t k e y . P 1 ,1 4 ,4 0 ,0 2 ,2

7 ,7 8 ,8 Implementation with an Sorted Sequence Let S be a sequence. A pair of key and element is denoted as p=(k,e). With an sorted sequence, we can easily extract the element with the smallest key with the combination of methods remove() and first() of S. However, to perform operation insertItem, we need to scan through the sequence S to find the apropriate position to insert the new element and key. E x a m p le : T o in s e rt th e p a ir (6 ,6 ), w e h a v e to s c a n th ro u g h th e s e q u e n c e u n til w e f in d th e r ig h t p la c e ( b e tw e e n ( 4 ,4 ) a n d ( 7 ,7 ) ) .

P 0 ,0 1 ,1 2 ,2 4 ,4 7 ,7 6 ,6 8 ,8 Comparing the Two Implementations Assume that the size of the sequence is n.

Method Unsorted S Sorted S size, isEmpty fast fast insertItem fast minElement, minKey, removeMin fast Class SortedSequencePriorityQueue public class SortedSequencePriorityQueue implements PriorityQueue { protected Sequence S = new NodeSequence(); protected Comparator comp; protected Object key( Position pos ) {

return (( Item )pos.element()).key(); } protected Object elem( Position pos ) { return (( Item )pos.element()).element(); } protected Object elem( Object kep ) { return (( Item )kep ).element() } public SortedSequencePriorityQueue( Comparator c ) { comp = c; } public int size() { return S.size(); } public boolean isEmpty() { return S.isEmpty() } public void insertItem( Object k, Object e ) throws InvalidKeyException {

if( !comp.isComparable( k )) throws new InvalidKeyException( "The key is not valid" ); else if( S.isEmpty()) S.insertFirst( new Item( k, e )); else if( comp.isGreaterThan( k,key(S.last()))) S.insertAfter( S.last(), new Item( k, e )); else { Position curr = S.first(); while( comp.isGreaterThan( k, key( curr ))) curr = S.after( curr ); S.insertBefore( curr, new Item( k, e )); } } curr P

0,0 1,1 2,2 4 ,4 7 ,7 6 ,6 k = 6, e = 6 8 ,8 public Object removeMin()

throws PriorityQueueEmptyException { if( S.isEmpty()) throw new PriorityQueueEmptyException( "The priority queue is empty" ); else return elem( S.remove( S.first())); } Selection Sort and Insertion Sort Recall that we can use a priority queue to sort elements. Depending on whether a sorted sequence is used to implement the priority queue, we have two kinds of sort. If the priority queue is implemented with an unsorted sequence, it is called selection-sort. The table here shows the performance of selection sort on

sequence (7, 4, 8, 2, 5, 3, 9). Input Phase 1 Phase 2 Sequence S (7, 4, 8, 2, 5, 3, 9) (4, 8, 2, 5, 3, 9) (8, 2, 5, 3, 9) () (2) (2, 3) (2, 3, 4) (2, 3, 4, 5)

(2, 3, 4, 5, 7) (2, 3, 4, 5, 7, 8) (2, 3, 4, 5, 7, 8, 9) Priority Queue P () (7) (7, 4) (7, 4, 8, 2, 5, 3, 9) (7, 4, 8, 5, 3, 9) (7, 4, 8, 5, 9) (7, 8, 5, 9) (7, 8, 9) (8, 9) (9)

() If the priority queue is implemented with a sorted sequence, the sort is called insertion sort. The table here shows the performance of insertion sort on the same sequence S = (7, 4, 8, 2, 5, 3, 9). Input Phase 1 Phase 2 Sequence S (7, 4, 8, 2, 5, 3, 9) (4, 8, 2, 5, 3, 9) (8, 2, 5, 3, 9) (2, 5, 3, 9)

(5, 3, 9) (3, 9) (9) () (2) (2, 3) (2, 3, 4, 5, 7, 8, 9) Priority Queue P () (7) (4, 7) (4, 7, 8) (2, 4, 7, 8) (2, 4, 5, 7, 8)

(2, 3, 4, 5, 7, 8) (2, 3, 4, 5, 7, 8, 9) (7, 4, 8, 5, 3, 9) (7, 4, 8, 5, 9) () The table here is a comparison of running time for both kinds of sort. Selection Sort Insertion Sort Phase 1 Phase 2 Overall Recall that the runnint time for bobble sort is also propotional to the size of the square of n, the size of the sequence.

Data Structure Exercises 15.1