Project 04Data structures and algorithms, joint academic project
Clinic Queue Manager
Clinic queues, early departures, and workload statistics in logarithmic time, built on four coordinated 2-3 tree indexes in Java.
My role
Designed and built jointly with Guy Nadjharov. I primarily contributed the algorithmic thinking and the choice of 2-3 trees. The design keeps four balanced trees in sync: each doctor holds direct references to its own queue and workload entry, each queued patient points to its record, and workload ranges are answered from subtree counts and sums instead of scanning doctors.
Project overview
Problem
Manage doctors, FIFO patient queues, early departures, and workload-range statistics within logarithmic time bounds, without ready-made data structures.
Objective
Meet the required time and space bounds for every operation, including removing a patient from the middle of a queue and counting doctors by workload without scanning them.
Tech stack
Languages and tools
- Java
Methods
- Augmented 2-3 trees
- Subtree aggregates
- Coordinated indexes
- Complexity analysis
Architecture and implementation
A 2-3 tree is a search tree in which every internal node has two or three children and all leaves sit at the same depth. That balance keeps every search and update logarithmic. One generic implementation is reused for four indexes that are kept in sync on every update.
Index doctors and patients
One tree keys doctors by ID and another keys patients by ID. Each doctor node stores the patient count, the next patient, a reference to the doctor's workload entry, and the doctor's own queue tree.
Keep queues in FIFO order
Each doctor's queue is keyed by an arrival number from one global counter, so the minimum is always the earliest arrival. A patient's stored doctor ID and arrival number also allow removal from the middle of a queue.
Order doctors by workload
The workload tree uses (patient count, doctor ID) keys, so equal workloads stay distinct. A key cannot change in place, so each update removes and reinserts it.
Answer range queries from subtree totals
Every workload subtree caches its doctor count and total load. A range query totals the doctors up to b, subtracts those below a, and divides for the average, without visiting individual doctors.
Cache ordinary queries
Cached patient counts and next-patient IDs answer everyday queue questions without traversing the queue.
Each doctor node references its own queue tree and its entry in the workload tree. Each queue entry references the patient's node. A patient record stores its doctor ID and arrival number, which are used as keys when a patient leaves early. Workload-range queries subtract one subtree total from another.
| Operation | Time |
|---|---|
| Initialization | O(1) |
| Doctor entry or departure | O(log D) |
| Patient arrival, service, or early departure | O(log D + log P) |
| Queue count or next patient | O(log D) |
| Patient-to-doctor lookup | O(log P) |
| Workload-range count or average | O(log D) |
| Space | O(D + P) |
Outcomes and links
34450/34450
Random operations passed in official grading, alongside PPR 11/11. Graded 100/100.
Official course feedback
Results
| GradeOfficial coursework result | 100/100 |
|---|---|
| Official feedbackPPR 11/11, random operations 34450/34450 | All tests passed |
| Later reference-model checkComparisons and expected-exception checks over 10 deterministic runs of 3,000 operations | 3,983,645 |
The grade and feedback are the official results. The reference-model check was added later and is not part of the grading.
Takeaways and limits
- Caching subtree counts and loads turns a workload-range question into two walks down the tree, so it costs O(log D) instead of a scan of every doctor.
- Storing each patient's doctor ID and arrival number lets an early departure leave the middle of a queue in logarithmic time, without searching the queue.
- This is a single-threaded, in-memory academic implementation without persistence or real patient data.