# Managing Data by Priority Let's start with a data-structure design problem. **Design Problem**: A hospital emergency room needs to manage information about the patients who need to be seen. Patients are treated in order of urgency (most urgent first). As each person comes in, a record is created with their name, urgency level (a number, in which higher numbers have higher priority), and a brief description of their injury. Think about the kinds of operations that we have studied on ordered sequences of data this semester: - add - remove - get by position - contains **Question:** Which of these seem most important when managing the order in which to treat patients? Which operations need to be the most efficient? Assuming a busy emergency room, we will frequently be adding and removing patients. We only need to get the most urgent patient by position (we don't need to get patients in arbitrary positions). We also are unlikely to need to check whether a patient is in the data structure, since our focus is on maintaining the order of patients for treatment. Therefore, our priorities in term of efficiency are to add and remove quickly, as well as to get the first/most urgent patient quickly. **Question:** Consider the data structures that we have studied so far: which seem to be suitable here? Configure your choice with the types of the contents. - Linked List - Array List - Array - Tree/Binary Search Tree - Hashmap/Dictionary - HashSet/set - Graph Hashsets are out since the data need to be ordered. Graphs feel like overkill since the only relationship we have between patients is priority ordering, which is more suitable for a list or array. Let's explore the list/array options. What would we make lists of? How would we configure them? And what run-time would we be looking at for our key operations? **Option 1:** We could make a `LinkedList<Patient>` or `ArrayList<Patient>` in which patients were stored in order from highest to lowest priority. - This would make accessing the highest priority patient constant time (they would always be in the first position) - We could remove that first patient in constant time - Adding a patient would be linear-time because we'd have to traverse the list to find the right spot in which to insert the patient based on priority **Option 2:** We could speed up inserting patients by leveraging array indices. If we think of each index as a priority, we would insert each patient into some inner data structure within each priority. Something like: ```=java LinkedList<Patient>[] # an array of lists of patients ``` The outer ArrayList would have one entry per priority level (say 1 to 10). In terms of runtime: - adding a patient *could* be constant time if we don't want to distinguish among patients with the same priority ranking (otherwise we might need some sort of order within each LinkedList, which could still leave us at linear time in the worst case). - getting (and removing) the highest priority patient is constant time, but we do need to be able to figure out which array index is the highest priority with patients stored (maybe there are only medium-priority patients at the current time). We could address this by tracking the highest-priority index that's in use, say doing something like: ```=java class PatientPriorities { LinkedList<Patient>[] patients; int highestIndexInUse; public void addPatient(Patient p, int priority) { this.patients[priority].add(p); # update the highest priority index if necessary if (priority > highestIndexInUse) this.highestIndexInUse = priority; } public Patient getNextPatient() { # return first patient in highest priority index return patients[highestIndexInUse].get(0); # may have to update highestIndexInUse ... } } ``` Option 2 may feel like an improvement over Option 1, but managing the indices is annoying (which suggests that perhaps this isn't the best design). Furthermore, this solution doesn't generalize very well. Our use of array indices exploited an assumption that we only have integers as priorities. What if our priority computation resulted in real/float numbers in the range 1 to 10. In that case, the array indices are no longer viable. The idea of mapping priorities to patients still has appeal, however -- perhaps we should try a HashMap? **Option 3:** Let's make a HashMap or Dictionary from priorities to lists of Patients ``` HashMap<Float,LinkedList<Patient>> ``` This has the advantage that any priority value can be used as a key. It has the significant downside that the keys are completely unordered, so finding (or tracking) the key with the highest-priority value still requires searching through all the keys (a linear-time operation in the number of keys). Is this really an improvement over our earlier options? **Stepping back:** Lists of Patients offer a clean design --- there's none of this key management, we just store the patients in order. It has a bit of overhead to maintain that order, but is that overhead really worse than maintaining ordering information on keys? The key-management overhead might cost less in some cases than the Patient-order overhead in terms of runtime, but it just feels clumsy. If only we didn't have to pay linear-time to insert new Patients into a list of patients in sorted order! Turns out, we can keep the best features of lists AND get a better runtime if we instead build our solution on trees.