Priority-Queues Notes | EduRev

: Priority-Queues Notes | EduRev

 Page 1


10/20/2014 7:46 PM Priority Queues 1 
Priority Queues 
Sell 100 IBM $122 
Sell 300 IBM $120 
Buy 500 IBM $119 
Buy 400 IBM $118 
Page 2


10/20/2014 7:46 PM Priority Queues 1 
Priority Queues 
Sell 100 IBM $122 
Sell 300 IBM $120 
Buy 500 IBM $119 
Buy 400 IBM $118 
10/20/2014 7:46 PM Priority Queues 2 
Outline and Reading 
PriorityQueue ADT (§7.1) 
Total order relation  (§7.1.1) 
Comparator ADT (§7.1.4) 
Sorting with a priority queue (§7.1.2) 
Selection-sort  (§7.2.3) 
Insertion-sort (§7.2.3) 
Page 3


10/20/2014 7:46 PM Priority Queues 1 
Priority Queues 
Sell 100 IBM $122 
Sell 300 IBM $120 
Buy 500 IBM $119 
Buy 400 IBM $118 
10/20/2014 7:46 PM Priority Queues 2 
Outline and Reading 
PriorityQueue ADT (§7.1) 
Total order relation  (§7.1.1) 
Comparator ADT (§7.1.4) 
Sorting with a priority queue (§7.1.2) 
Selection-sort  (§7.2.3) 
Insertion-sort (§7.2.3) 
10/20/2014 7:46 PM Priority Queues 3 
Priority Queue ADT 
A priority queue stores a 
collection of items 
An item is a pair 
(key, element) 
Main methods of the Priority 
Queue ADT 
? insertItem(k, o) 
inserts an item with key k 
and element o 
? removeMin() 
removes the item with the 
smallest key 
Additional methods 
? minKey(k, o) 
returns, but does not 
remove, the smallest key of 
an item 
? minElement() 
returns, but does not 
remove, the element of an 
item with smallest key 
? size(), isEmpty() 
Applications: 
? Standby flyers 
? Auctions 
? Stock market 
Page 4


10/20/2014 7:46 PM Priority Queues 1 
Priority Queues 
Sell 100 IBM $122 
Sell 300 IBM $120 
Buy 500 IBM $119 
Buy 400 IBM $118 
10/20/2014 7:46 PM Priority Queues 2 
Outline and Reading 
PriorityQueue ADT (§7.1) 
Total order relation  (§7.1.1) 
Comparator ADT (§7.1.4) 
Sorting with a priority queue (§7.1.2) 
Selection-sort  (§7.2.3) 
Insertion-sort (§7.2.3) 
10/20/2014 7:46 PM Priority Queues 3 
Priority Queue ADT 
A priority queue stores a 
collection of items 
An item is a pair 
(key, element) 
Main methods of the Priority 
Queue ADT 
? insertItem(k, o) 
inserts an item with key k 
and element o 
? removeMin() 
removes the item with the 
smallest key 
Additional methods 
? minKey(k, o) 
returns, but does not 
remove, the smallest key of 
an item 
? minElement() 
returns, but does not 
remove, the element of an 
item with smallest key 
? size(), isEmpty() 
Applications: 
? Standby flyers 
? Auctions 
? Stock market 
10/20/2014 7:46 PM Priority Queues 4 
Total Order Relation 
Keys in a priority 
queue can be 
arbitrary objects 
on which an order 
is defined 
Two distinct items 
in a priority queue 
can have the 
same key 
 
Mathematical concept 
of total order relation = 
? Reflexive property: 
x = x 
? Antisymmetric property: 
x = y ? y = x ? x = y 
? Transitive property: 
 x = y ? y = z ? x = z 
Page 5


10/20/2014 7:46 PM Priority Queues 1 
Priority Queues 
Sell 100 IBM $122 
Sell 300 IBM $120 
Buy 500 IBM $119 
Buy 400 IBM $118 
10/20/2014 7:46 PM Priority Queues 2 
Outline and Reading 
PriorityQueue ADT (§7.1) 
Total order relation  (§7.1.1) 
Comparator ADT (§7.1.4) 
Sorting with a priority queue (§7.1.2) 
Selection-sort  (§7.2.3) 
Insertion-sort (§7.2.3) 
10/20/2014 7:46 PM Priority Queues 3 
Priority Queue ADT 
A priority queue stores a 
collection of items 
An item is a pair 
(key, element) 
Main methods of the Priority 
Queue ADT 
? insertItem(k, o) 
inserts an item with key k 
and element o 
? removeMin() 
removes the item with the 
smallest key 
Additional methods 
? minKey(k, o) 
returns, but does not 
remove, the smallest key of 
an item 
? minElement() 
returns, but does not 
remove, the element of an 
item with smallest key 
? size(), isEmpty() 
Applications: 
? Standby flyers 
? Auctions 
? Stock market 
10/20/2014 7:46 PM Priority Queues 4 
Total Order Relation 
Keys in a priority 
queue can be 
arbitrary objects 
on which an order 
is defined 
Two distinct items 
in a priority queue 
can have the 
same key 
 
Mathematical concept 
of total order relation = 
? Reflexive property: 
x = x 
? Antisymmetric property: 
x = y ? y = x ? x = y 
? Transitive property: 
 x = y ? y = z ? x = z 
10/20/2014 7:46 PM Priority Queues 5 
Comparator ADT 
A comparator encapsulates the action of comparing 
two objects according to a given total order 
relation 
A generic priority queue uses a comparator as a 
template argument, to define the comparison 
function (<,=,>) 
The comparator is external to the keys being 
compared.  Thus, the same objects can be sorted 
in different ways by using different comparators. 
When the priority queue needs to compare two 
keys, it uses its comparator 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!