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

  1. (2 points.) Suppose that a passenger is defined per the below, wherein group 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;
  2. (3 points.) In several lines of pseudocode, describe an algorithm via which to enqueue a passenger into your pqueue.

  3. (2 points.) What’s the upper bound on that algorithm’s running time? Why?

  4. (3 points.) In several lines of pseudocode, describe an algorithm via which to dequeue a passenger from your pqueue. If multiple passengers happen to have the same priority, any of them may be dequeued first.

  5. (2 points.) What’s the upper bound on that algorithm’s running time? Why?

Debrief

  1. Which resources, if any, did you find helpful in answering this problem’s questions?

  2. About how long did you spend on this problem’s questions?