Zombie ambulance

In this problem, you are going to implement a double-ended priority queue using a skip list. You will then use this data structure to simulate an important and realistic healthcare scenario.

Double-Ended Priority Queue

A DEPQ is like a priority queue (e.g., heap) that supports both delete-max and delete-min. Specifically, it should support the following operations:

• insert(k,v): Inserts a new element with the given priority k and associated value v
• deleteMin(): Removes the element with the least priority, and returns both this element's priority and associated value.
• deleteMax(): Removes the element with the greatest priority, and returns both this element's priority and associated value.

Your program will use a DEPQ, which you should implement using a skip list. To help get you started you might want to use my incomplete skip list class in Java, C++, or Python:

• skiplist.py
• skiplist.cpp
• SkipList.java

My implementation already contains the insert method, which you just need to complete by making the height be chosen randomly instead of always being 1. (See also problem 45.) You will need to write the deleteMin and deleteMax operations yourself of course. I should also point out that it is allowed to have multiple items with the same priority; it doesn't matter in which order these get removed.

Zombies

Here's the situation: There is a zombie outbreak in DTA and no one is safe. Fortunately, a popular beverage (the "antidote") has been found to reverse and prevent the spread of the zombie virus in humans. Now you have an old ambulance and are driving around stocking up on the antidote and administering it to the infected humans you encounter.

When your ambulance comes across an infected human, you always take them into the vehicle right away. Since your ambulance has a limited capacity, this might mean that you have to kick someone else out. You always choose to kick out the MOST healthy person, in the hopes of picking them up later.

When your ambulance comes across some antidote, you take all of it and administer it immediately to the people in the ambulance, starting with the LEAST healthy. As soon as someone gets the antidote, they leave the ambulance. If there's extra antidote and no more passengers, you drink it immediately (no stockpiling).

Details

Your program will be run with a single command-line argument that indicates the capacity of the ambulance, not including the driver. For example, running

java Prob 15

means to start your program with a 15-passenger zombie ambulance.

The input to your program is simply the series of infected humans and antidote stores that you encounter as you drive around. This will come from standard in as a series of lines like

HUMAN 23 Greg
HUMAN 67.2 Bobby
HUMAN 0.88 Marcia
ANTIDOTE 2
HUMAN 40 Peter
HUMAN 41 Cindy
ANTIDOTE 1
ANTIDOTE 10
HUMAN 2 Jan

Each line of input either starts with HUMAN and is followed by their health rating (higher means healthier) and name, or it starts with ANTIDOTE and is followed by the number of doses found.

The output from your program should also have two kinds of lines: a line of output that starts with HEALED, followed by a name, means that person received a dose of the antidote and left the ambulance healthy. A line of output that starts with SICK means that person was kicked out of the ambulance because you ran out of room. (Remember that the most healthy are kicked out first.)

For the input above, if the capacity of the ambulance is 15, the correct output would be

HEALED Marcia
HEALED Greg
HEALED Peter
HEALED Cindy
HEALED Bobby

However, if the capacity of the ambulance were set to just 1, the output would look different:

SICK Bobby
SICK Greg
HEALED Marcia
SICK Cindy
HEALED Peter

Bonus #1

2 bonus points will be awarded to any DEPQ implementation that supports deleteMin and deleteMax in \(O(1)\) time. To make this possible, the main change you will have to make to my skip list implementation would be to add backward links, making all the levels doubly-linked lists. If I were you, I would do this by adding another list of links called blinks to the Tower class.

Bonus #2

Up to 2 bonus points are available if you add another feature to your program: passengers may become zombies. At each iteration of the algorithm (each time a new HUMAN or ANTIDOTE is picked up), each current passenger might become a zombie with some probability. Specifically, if a passenger has health rating h, they will become a zombie at any given step with probability

\[\frac{1}{(h+1)^2}\]

(So for example, someone with a low health rating like 0.5 has a fairly high likelihood, \(\frac{4}{9}\), of turning into a zombie. Someone with a high health rating like \(50\) has a much lower chance of turning into a zombie, only about .038% chance.)

When a passenger turns into a zombie, they eat all the other passengers (but not the driver) and run out of the ambulance. Your program should merely record this with a line such as

ZOMBIE Marcia

and by emptying the DEPQ completely to essentially start over.

Submit your program according to the instructions on the submit page.