Heap Patterns Example: The Middle Waiting Time as Each Patient Arrives

A max-heap of the shorter half and a min-heap of the longer half keep the middle at their two tops, however many times arrive.

Two heaps keep the middle of a growing list of values at their tops, so the middle is ready after every arrival without sorting again. A clinic's screen shows the median waiting time, the middle value when the times are in order, or the average of the two middle values when there is an even number of them. Patients so far waited 12, 30, 7, 18 and 25 minutes, and the screen updates after each one. The question never mentions a heap; the cue is a middle that has to stay current while values keep arriving.

What does the screen show after the fourth patient?

15 minutes. In order the four times are 7 12 18 30, and the two middle values, 12 and 18, average 15.

The lower half of the times goes in a max-heap, whose top is the largest of the short waits, and the upper half in a min-heap, whose top is the smallest of the long ones. Two invariants hold after every arrival: every value in the lower heap is at most every value in the upper heap, and the lower heap holds the same number of values as the upper or one more. A new time is pushed into the lower heap, the lower heap's top moves to the upper heap, and if the upper heap is then larger, its top moves back. The middle is then the lower heap's top, or the average of the two tops when the sizes are equal.

The run prints both halves after each arrival, the lower half largest first and the upper half smallest first, so each heap's top is the value beside the middle.

The two halves and the middle after each arrival, from the run
Arrival	Lower half (max-heap)	Upper half (min-heap)	Middle
12	12	Empty	12
30	12	30	21
7	12 7	30	12
18	12 7	18 30	15
25	18 12 7	25 30	18

Python's heapq has only a min-heap, so the lower half holds negated times, and its top, negated back, is the largest short wait.

median.pypy

import heapq

lower: list[int] = []
upper: list[int] = []


def add(value: int) -> float:
    heapq.heappush(lower, -value)
    heapq.heappush(upper, -heapq.heappop(lower))
    if len(upper) > len(lower):
        heapq.heappush(lower, -heapq.heappop(upper))
    if len(lower) > len(upper):
        return -lower[0]
    return (-lower[0] + upper[0]) / 2


for minutes in [12, 30, 7, 18, 25]:
    middle = add(minutes)
    low_half = sorted((-v for v in lower), reverse=True)
    print(f"{minutes:>2}: lower {low_half}, upper {sorted(upper)}, middle {middle:g}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

12: lower [12], upper [], middle 12
30: lower [12], upper [30], middle 21
 7: lower [12, 7], upper [30], middle 12
18: lower [12, 7], upper [18, 30], middle 15
25: lower [18, 12, 7], upper [25, 30], middle 18

Each arrival makes at most three pushes and pops of O(log n) each, and reading the middle is O(1), so n arrivals cost O(n log n) in total with O(n) space. Sorting the list again after each arrival costs O(n log n) each time, or O(n) to insert into a kept sorted list, either way O(n²) for the day. One heap alone cannot do it: a min-heap of every time knows only the shortest wait, not the middle.

Heaps

← → move through sections and cards