Priority Queue in Data Structures & Programming
Data Structures &
Programming
Priority Queue
Golnar Sheikhshab
Priority Queue models Life!
Modern life:
●
Need a loan? What's your credit-score?
●
Need a job? How skilled are you?
●
Need a scholarship? How well can you play X-ball?
In evolutionary theory
natural selection
is also known as
survival of the fittest
A little-less-modern life:
●
Need food? How fast are you?
●
Don't want to die? How strong are you?
Priority Queue ADT
●
Fundamentally different from the position-based data structures such as
stacks, queues, deques, lists, and even trees:
○
stores elements according to their priorities
○
has no external notion of “position”
Keys, Priorities, and Total Order Relations
●
key: and object assigned to an element by a user or application to identify,
rank, weigh it.
○
Not necessarily unique
○
is used in definition of order
○
can be complex
○
can be extracted from the element or not
●
Total order (over keys)
○
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
○
Then a minimum is well-defined
An Application of Priority Queue
E
x
a
m
p
l
e
8
.
1
:
S
u
p
p
o
s
e
a
c
e
r
t
a
i
n
f
l
i
g
h
t
i
s
f
u
l
l
y
b
o
o
k
e
d
a
n
h
o
u
r
p
r
i
o
r
t
o
d
e
p
a
r
t
u
r
e
.
B
e
c
a
u
s
e
o
f
t
h
e
p
o
s
s
i
b
i
l
i
t
y
o
f
c
a
n
c
e
l
l
a
t
i
o
n
s
,
t
h
e
a
i
r
l
i
n
e
m
a
i
n
t
a
i
n
s
a
p
r
i
o
r
i
t
y
q
u
e
u
e
o
f
s
t
a
n
d
b
y
p
a
s
s
e
n
g
e
r
s
h
o
p
i
n
g
t
o
g
e
t
a
s
e
a
t
.
T
h
e
p
r
i
o
r
i
t
y
o
f
e
a
c
h
p
a
s
s
e
n
g
e
r
i
s
d
e
t
e
r
m
i
n
e
d
b
y
t
h
e
f
a
r
e
p
a
i
d
,
t
h
e
f
r
e
q
u
e
n
t
-
f
l
y
e
r
s
t
a
t
u
s
,
a
n
d
t
h
e
t
i
m
e
w
h
e
n
t
h
e
p
a
s
s
e
n
g
e
r
i
s
i
n
s
e
r
t
e
d
i
n
t
o
t
h
e
p
r
i
o
r
i
t
y
q
u
e
u
e
.
W
h
e
n
a
p
a
s
s
e
n
g
e
r
r
e
q
u
e
s
t
s
t
o
f
l
y
s
t
a
n
d
b
y
,
t
h
e
a
s
s
o
c
i
a
t
e
d
p
a
s
s
e
n
g
e
r
o
b
j
e
c
t
i
s
i
n
s
e
r
t
e
d
i
n
t
o
t
h
e
p
r
i
o
r
i
t
y
q
u
e
u
e
w
i
t
h
a
n
i
n
s
e
r
t
o
p
e
r
a
t
i
o
n
.
S
h
o
r
t
l
y
b
e
f
o
r
e
t
h
e
f
l
i
g
h
t
d
e
p
a
r
t
u
r
e
,
i
f
s
e
a
t
s
b
e
c
o
m
e
a
v
a
i
l
a
b
l
e
(
f
o
r
e
x
a
m
p
l
e
,
d
u
e
t
o
l
a
s
t
-
m
i
n
u
t
e
c
a
n
c
e
l
l
a
t
i
o
n
s
)
,
t
h
e
a
i
r
l
i
n
e
r
e
p
e
a
t
e
d
l
y
r
e
m
o
v
e
s
a
s
t
a
n
d
b
y
p
a
s
s
e
n
g
e
r
w
i
t
h
f
i
r
s
t
p
r
i
o
r
i
t
y
f
r
o
m
t
h
e
p
r
i
o
r
i
t
y
q
u
e
u
e
,
u
s
i
n
g
a
c
o
m
b
i
n
a
t
i
o
n
o
f
m
i
n
a
n
d
r
e
m
o
v
e
M
i
n
o
p
e
r
a
t
i
o
n
s
,
a
n
d
l
e
t
s
t
h
i
s
p
e
r
s
o
n
b
o
a
r
d
.
Comparators
Using Comparators
A C++ Priority Queue Interface
The STL priority queue Class
The STL priority queue Class
Implementing a Priority Queue with a (Sorted) List
A C++ Priority Queue Class Declaration
A C++ Priority Queue Implementation
Sorting with a Priority Queue
Selection-Sort and Insertion-Sort with Priority Queue
PriorityQueueSort on an Implementation with Unsorted List => Selection Sort
PriorityQueueSort on an Implementation with Sorted List => Insertion Sort
Final Note
Is priority queue a special case of queue or is queue a special case of priority
queue?
Reading Material
Sections 8.1 - 8.3 of the textbook
Priority queues are fundamental data structures storing elements based on priorities rather than positions. Learn about priority queue models in modern life, the application of priority queues, key concepts like keys, priorities, total order relations, and more. Explore how priority queues are used to manage tasks efficiently based on importance and urgency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Data Structures & Programming Priority Queue Golnar Sheikhshab
Priority Queue models Life! Modern life: Need a loan? What's your credit-score? Need a job? How skilled are you? Need a scholarship? How well can you play X-ball? A little-less-modern life: Need food? How fast are you? Don't want to die? How strong are you? In evolutionary theory natural selection is also known as survival of the fittest
Priority Queue ADT Fundamentally different from the position-based data structures such as stacks, queues, deques, lists, and even trees: stores elements according to their priorities has no external notion of position
Keys, Priorities, and Total Order Relations key: and object assigned to an element by a user or application to identify, rank, weigh it. Not necessarily unique is used in definition of order can be complex can be extracted from the element or not Total order (over keys) Reflexive property : k k Antisymmetric property: if k1 k2 and k2 k1, then k1 = k2
An Application of Priority Queue Example 8.1: Suppose a certain flight is fully booked an hour prior to departure. Because of the possibility of cancellations, the airline maintains a priority queue of standby passengers hoping to get a seat. The priority of each passenger is determined by the fare paid, the frequent-flyer status, and the time when the passenger is inserted into the priority queue. When a passenger requests to fly standby, the associated passenger object is inserted into the priority queue with an insert operation. Shortly before the flight departure, if seats become available (for example, due to last-minute cancellations), the airline repeatedly removes a standby passenger with first priority from the priority queue, using a combination of min and removeMin operations, and lets this person board.
Selection-Sort and Insertion-Sort with Priority Queue PriorityQueueSort on an Implementation with Unsorted List => Selection Sort PriorityQueueSort on an Implementation with Sorted List => Insertion Sort
Final Note Is priority queue a special case of queue or is queue a special case of priority queue?
Reading Material Sections 8.1 - 8.3 of the textbook
