class PatientHeapQueue(PriorityQueue): """ Implement a queue structure using a 0-indexed heap. This particular type of queue holds patient information. """

def __init__(self, start_data=None):

""" Create the patient queue."""

if start_data is None: start_data = [] self.data = []

class EditablePatientHeapQueue(PatientHeapQueue): """ Implement a queue structure using a 0-indexed heap. This particular type of queue holds patient information. Additionally, we can remove patients not at the top of the heap in O(log n) time. """

def __init__(self, start_data=None): self.indices = {} # name -> index; # Keep track of where patients are stored for (i, person) in enumerate(start_data): self.indices[person.name] = i super().__init__(start_data)

def _swap(self, i, j): """ Swap patients at index i and j. Don't forget to change their position in self.indices as well! """

def remove(self, patient_name): """ Remove the particular patient from the heap. Remember, the index will tell you where the patient is in the heap and every sub-heap below an index forms a valid heap. """

def enqueue(self, patient): """ Add a patient to the queue. """

def dequeue(self): """ Remove a patient from the front of the queue and return them. """

For this task, you will be implementing an EditablePatientHeapQueue, which enables arbitrary patient deletion (by name) n Oogn) time using a new remove method. As with most efficiency improvements, we have traded space for time: we will store the index of every patient in a Python dictionary self.indices, keyed by their name. This way, finding a patient is O(1) time, so the dominant operation is the subsequent sifting of the replacement. The wrinkle in the plan is that we need to keep track of where a patient is stored, even when sifting. For this reason, you should provide a new version of the enqueue, dequeue, and_svap methods which take the new self.indices dictionary into account. For this task, you will be implementing an EditablePatientHeapQueue, which enables arbitrary patient deletion (by name) n Oogn) time using a new remove method. As with most efficiency improvements, we have traded space for time: we will store the index of every patient in a Python dictionary self.indices, keyed by their name. This way, finding a patient is O(1) time, so the dominant operation is the subsequent sifting of the replacement. The wrinkle in the plan is that we need to keep track of where a patient is stored, even when sifting. For this reason, you should provide a new version of the enqueue, dequeue, and_svap methods which take the new self.indices dictionary into account