Now Boarding
A "priority queue" is a queue wherein each element has a "priority" associated with it. Elements with higher priority are dequeued before elements with lower priority. Airlines tend to use priority queues when boarding planes; passengers in "group 1" might be asked to board before passengers in "group 2" and so forth.
Answer the below in pqueue.md
.
Questions
-
(2 points.) Suppose that a
passenger
is defined per the below, whereingroup
represents a passenger’s priority.typedef struct { unsigned int group; } passenger;
Complete the definition of
pqueue
below in such a way that it represents a priority queue for passengers.typedef struct { // TODO } pqueue;
-
(3 points.) In several lines of pseudocode, describe an algorithm via which to enqueue a
passenger
into yourpqueue
. -
(2 points.) What’s the upper bound on that algorithm’s running time? Why?
-
(3 points.) In several lines of pseudocode, describe an algorithm via which to dequeue a
passenger
from yourpqueue
. If multiplepassenger
s happen to have the same priority, any of them may be dequeued first. -
(2 points.) What’s the upper bound on that algorithm’s running time? Why?
Debrief
-
Which resources, if any, did you find helpful in answering this problem’s questions?
-
About how long did you spend on this problem’s questions?