patient_index will be indexing beyond the end of self.data.įor the future, you might consider learning how to use the debugger to add breakpoints and single-step your code. You might want to consider what happens next if the item you're deleting is the last item on the heap.
In your remove method, you have this: #Remove the patient from the heap and dictionary I'd suggest replacing this line: del self.indices
#PYTHON PRIORITY QUEUE DELETE ELEMENT CODE#
Otherwise your code is going to fail when it tries to sift that item down.įor the delete error, I think your problem is that you're trying to index indices by the patient rather than the patient name. That's fine, but then you have to change its index in the dictionary. On the second line, you move the item from the end of the heap to the top of the heap. In the elif case, you have to remove the item from self.indices. In your dequeue method, you have this code: elif len(self.data) = 1: So when you try to look up a patient name in the dictionary, it's not there. The first is that you're not adding an entry to self.indices when you enqueue an item. I am getting the following error- 1 builtins.AssertionError: Heap invariant violated!/AssertionError: Bad heap invariant after 'remove': """ Remove a patient from the front of the queue and return them. #Patient index is greater than parent then sift up #Parent is greater than patient index then sift down #Remove the patient from the heap and dictionary #Retrieve the index for the patient name in O(1) time #Step 1: Find the patient in O(1) time and remove from the heap and dictionary #Dictionary self.indices- key (patient name) : value (index) The index will tell you where the patient is in the heapĪnd every sub-heap below an index forms a valid heap. """ Remove the particular patient from the heap.
Self.data, self.data = self.data, self.data # Keep track of where patients are storedįor (i, person) in enumerate(start_data): """ĭef _init_(self, start_data=None, fast=False): Additionally, we can remove patients not at the top of the heap in O(log n) time. This particular type of queue holds patient information. """ Implement a queue structure using a 0-indexed heap. My implementation class EditablePatientHeapQueue(PatientHeapQueue): For this reason, you should provide a new version of the enqueue, dequeue, and _swap methods which take the new self.indices dictionary into account." The wrinkle in the plan is that we need to keep track of where a patient is stored, even when sifting. This way, finding a patient is O(1) time, so the dominant operation is the subsequent sifting of the replacement. 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. I am working on the following- "For this task, you will be implementing an EditablePatientHeapQueue, which enables arbitrary patient deletion (by name) in O(log n) time using a new remove method.
0 kommentar(er)
