Module assignment: heaps in Python

What you will build

This assignment brings the whole module together in one program. You will build the software for a small triage desk. Patients arrive at a clinic and wait to be seen. The most urgent patient is seen first. Patients with equal urgency are seen in the order they arrived. The desk manager also wants two views: a list of the next few patients to call, and the median of how long patients have waited. Both views must stay correct while patients come and go.

You will use three ideas from the module. A heap is a list arranged so that its smallest item is always at index 0, which is the first position. A priority queue is a line where the most important item leaves first, and a heap is how Python builds one. Lesson 2 gave you the heap with a sort key that handles ties. Lesson 3 gave you the top-K view, which reads the best K items from a heap without changing it. Lesson 4 gave you the two-heap median, which reads the middle value after every change. The program reads one command per line, so you can test it the way a real desk would use it.

There is no shortcut that skips the heap. A sorted list would give the same answers on small inputs, and it would also pass some tests. The rubric below rewards a solution that uses heaps where the lessons show them, and that keeps every operation at its heap cost.

The specification

The program reads commands from standard input until the input ends. Standard input is the text the program receives, such as lines typed in or a file given to the program. Each command is one line. Words are separated by single spaces. Empty lines are ignored. Any line whose first word is not one of the five commands below is ignored as well.

Here are the rules that a grader checks.

The order of next is strictly by urgency, then by arrival. Two patients with the same urgency never swap places. A patient seen by next is gone, so later next and top commands must not see that patient again.

The top K command must not change the waiting room. Run it, then run next again, and the same patient must come out first as before.

The median is the median of the recorded wait times. When there are an even number of recorded waits, average the two middle values. When there are an odd number, use the middle one.

Limits: at most 2,000 lines. URGENCY, MINUTES and K are between 1 and 100,000, and K is at least 1 in every top line.

Examples

Here is the first example. Read the input line by line and follow the rules, then check your output against the one shown.

Input:

arrive Asha 3
arrive Ben 5
arrive Chen 3
top 2
next
arrive Dee 5
next
wait 12
wait 20
wait 7
median
next
next
next
next

Output:

Ben Asha
Ben
Dee
12.0
Asha
Chen
none
none

Trace the first lines. Asha arrives with urgency 3, then Ben with 5, then Chen with 3. top 2 looks at the two most urgent: Ben, with 5, and then Asha, with 3, because Asha arrived before Chen. The output is Ben Asha. Nobody leaves the room. The next line then sees Ben, the most urgent, and prints Ben.

Dee arrives with 5. The room now holds Dee (5), Asha (3) and Chen (3). next prints Dee. The three waits, 12, 20 and 7, are recorded. Sorted, they are 7, 12 and 20, so the median is 12.0. The last four next lines print Asha, Chen, then none twice.

Here is the second example. It tests the empty room, the unknown line, and the median of an even count.

Input:

top 3
median
next
arrive A 1
top 5
wait 4
wait 10
median
wait 1
median
hello there

Output:

none
none
none
A
7.0
4.0

The first three lines print none because nothing has happened yet. arrive A 1 adds one patient, and top 5 prints the one name in the room. The waits 4 and 10 give an even count, so the median is (4 + 10) / 2 = 7.0. Adding 1 makes three values, sorted 1, 4, 10, so the median is 4.0. The line hello there starts with an unknown command, so the program ignores it and prints nothing.

The checklist

Work through this list before you call the assignment finished. Each item is something a grader checks.

• The program reads all lines until the input ends, and it skips empty lines.
• The arrive command stores the name, the urgency, and an arrival number that increases by one for each patient.
• The waiting room is a heap of tuples, such as (-urgency, arrival, name). The smallest tuple is the most urgent patient, and ties go to the smaller arrival number.
• You can explain why the urgency is negated, given that heapq is a min-heap and has no comparator argument.
• The next command prints none when nobody is waiting, and removes the patient it prints.
• The top K command copies the room, so the original room does not change.
• The top K command prints at most K names, and prints all names when fewer are waiting.
• The top K command prints none when nobody is waiting.
• The wait command keeps the median with two heaps, using the three-step add from lesson 4.
• The median command prints one digit after the decimal point, with an f-string such as f"{value:.1f}", and prints none before the first wait.
• The median command averages the two middle values when the count is even, and divides by 2.
• Unknown lines are ignored without an error.
• The program produces the exact output for both examples above.
• You can explain in two sentences why top K copies the heap before reading it.
• You can state the time cost of arrive, next, top K, wait and median.

Grading rubric

A grader scores the program against three levels. Each level describes what a solution at that level does.

A 60 percent solution handles the basic flow. It accepts arrive and next, and it returns patients in urgency order with arrival ties. It prints none when the room is empty. It may fail the top and median lines, or print them wrongly. The program is a heap with a correct key, and its next lines match the first example.

An 80 percent solution handles every command in the table. The top K command prints the right names in the right order, and it does not change the room. The wait and median commands are correct for odd and even counts. The program also handles none for all commands, and it ignores unknown lines. It passes both examples exactly. The weakness is usually the median, which may use a sort on every median call, or the top-K view, which may remove patients from the real room.

A 100 percent solution does everything in the 80 percent level, and it uses the costs the module teaches. arrive and next cost O(log n). top K costs O(K log n) for the pops from the copy, plus O(n) for the copy itself, because list(room) copies every item. wait costs O(log n) with the two-heap add. median costs O(1). The code is clear, the keys use negation for urgency, the median divides by 2, and each command has one small function or one clear block. The program also handles a long input of 2,000 lines without slowing down.

When you explain your work, a 100 percent solution names the heap for each job and says why the sizes stay correct. A solution that cannot explain its two heaps is capped at the 80 percent level, even if its output is right.

Hints

Try the assignment yourself before reading the hints. Each hint has its own heading, so read them one at a time.

Hint 1: the room

Use a list as a heap, with heapq.heappush to add and heapq.heappop to remove the smallest item. Store each patient as a tuple, such as (-urgency, arrival, name). A tuple is a fixed group of values in parentheses. Python compares tuples one item at a time, from left to right. heapq has no comparator argument, so the negation turns "biggest urgency first" into "smallest key first". The arrival number breaks ties, because the patient who came first has the smaller number. Arrival numbers are never equal, so the name is never compared.

Hint 2: reading the lines

Loop over the lines of the input. line.split() splits on spaces and drops extra spaces. An empty line gives an empty list, so if not parts: skips it. Use parts[0] to choose the command. For an arrive line, parts[1] is the name and parts[2] is the urgency. Use int(...) to turn the text into a number.

Hint 3: top K without damage

Make a copy with list(room). A copy of a heap list is still a heap, because it has the same items in the same order. Pop from the copy up to K times and collect the names. The real room is not touched. The copy takes O(n) time, which is why the rubric counts it.

Hint 4: the median

Use two heaps. low holds the smaller half of the waits, and it must give its largest value first. Python has no max-heap, so store negative numbers in low. high holds the larger half as plain numbers, and its smallest value comes first. For each wait, push the value into low, move the top of low to high, and move the top of high back to low if high has more items. Then the median is the top of low when low has more items, or the average of both tops when the counts are equal.

Hint 5: printing

Print none when there is nothing to show. Format the median with f"{value:.1f}". f"{12:.1f}" gives 12.0, so a whole number still prints a decimal digit. Python's / always gives a float, so (a + b) / 2 is safe. Python's number formatting does not depend on the locale setting, so you do not need to pass a locale.

The spec does not say how to round an exact half. Python rounds it to the even digit. For example, f"{7.25:.1f}" gives 7.2, and f"{7.75:.1f}" gives 7.8. Collect the output in a list and print it once at the end.

Hint 6: testing

Run the first example and compare it line by line with the output above. Then test the empty room, a room with two patients of equal urgency, and a top line with K bigger than the room. Last, write a test where the median count is odd and one where it is even. An assert line stops the program with an AssertionError when its check is false, which makes a small test easy to write.

Check your progress

Before you write the full program, you can check the first two commands with this program. It handles arrive and next only, and it ignores the other commands. It has the example input inside it, so it needs no typing. On the first example it prints Ben, Dee, Asha, Chen, then none twice. Those are the lines that come from the next commands in the expected output.

Use the output of this program to fix the room before you add the other commands. The top-K view and the median build on it.

Reference solution

The full solution is below. Try the assignment first. The solution is complete, and it passes both examples and the checklist. It is here so that you can compare it with your own after you have finished.

The program below has both examples inside it, so it runs as it is. To read real input, add import sys at the top and replace the two print lines in the main block with print(run_desk(sys.stdin.read()), end="").

Here is how the reference works, in case you want to compare. The room is a heap of tuples, so the smallest tuple is the next patient to see. The top branch copies the room and pops from the copy, so the real room is never touched. The wait branch is the three-step add from lesson 4, with low storing negative numbers so that it acts as a max-heap, and high storing plain numbers as a min-heap. The median branch reads the top of low when it has more values, and it averages the two tops when the counts are equal. Each command costs O(log n) or better, except top, whose copy costs O(n).

Stretch extension

If you finish early, add a remove NAME command. It takes a patient out of the room without seeing them, for example when a patient leaves the clinic. Think about how to do it in O(log n) time without searching the heap. Lesson 4 gives one answer: mark the patient as removed, and skip marked patients when they reach the top. This is called lazy deletion, because the marked item stays in the heap until it reaches the top. Test it with a patient in the middle of the room, and show that top and next both skip that patient.

What to submit

Write your program in one file named desk.py. Run it on both examples. Your output must match the expected output exactly, including the spacing and the decimal digit. Then write two sentences on the design: one on why the waiting room uses an arrival number as the tie rule, and one on why the median uses two heaps and what each heap holds.