Courses

# 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
Page 2

10/20/2014 7:46 PM Priority Queues 1
Priority Queues
Sell 100 IBM \$122
Sell 300 IBM \$120
10/20/2014 7:46 PM Priority Queues 2
Total order relation  (§7.1.1)
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
10/20/2014 7:46 PM Priority Queues 2
Total order relation  (§7.1.1)
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
A priority queue stores a
collection of items
An item is a pair
(key, element)
Main methods of the Priority
? insertItem(k, o)
inserts an item with key k
and element o
? removeMin()
removes the item with the
smallest key
? 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
10/20/2014 7:46 PM Priority Queues 2
Total order relation  (§7.1.1)
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
A priority queue stores a
collection of items
An item is a pair
(key, element)
Main methods of the Priority
? insertItem(k, o)
inserts an item with key k
and element o
? removeMin()
removes the item with the
smallest key
? 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
10/20/2014 7:46 PM Priority Queues 2
Total order relation  (§7.1.1)
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
A priority queue stores a
collection of items
An item is a pair
(key, element)
Main methods of the Priority
? insertItem(k, o)
inserts an item with key k
and element o
? removeMin()
removes the item with the
smallest key
? 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