다음 작업에 대해 -이 작업의 경우 새 제거를 사용하여 O (log n) 시간에 임의의 환자 삭제 (이름 별)를 가능하게하는 EditablePatientHeapQueue를 구현합니다 방법을 사용합니다. 대부분의 효율성 향상과 마찬가지로 우리는 공간을 시간적으로 교환했습니다 : 우리는 각 환자의 색인을 자신의 이름을 키로 한 Python 사전 self.indices에 저장합니다. 이렇게하면 환자를 찾는 것이 O (1) 시간이므로 계획의 주름은 체내에서 환자가 어디에 저장되어 있는지 추적해야하기 때문에 새 버전의 대기열에서 대기열에서 빼기, 새로운 self.indices 사전을 고려한 _swap 메쏘드 "우선 순위 대기열에서 임의의 요소 제거
나는 다음과 같은 오류 - 1 builtins.AssertionError을 얻고있다
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, fast=False):
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, fast)
def _swap(self, i, j):
""" Swap patients at index i and j. Don't forget to change
their position in self.indices as well!
"""
self.indices[self.data[i].name] = j
self.indices[self.data[j].name] = i
self.data[i], self.data[j] = self.data[j], self.data[i]
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.
"""
#Dictionary self.indices- key (patient name) : value (index)
#Heap self.data- patient name, priority
#Step 1: Find the patient in O(1) time and remove from the heap and dictionary
#Retrieve the index for the patient name in O(1) time
patient_index = self.indices[patient_name]
end = len(self.data)-1
#Swap patients
self._swap(patient_index, end)
#Remove the patient from the heap and dictionary
del self.data[end]
del self.indices[patient_name]
#Step 2: Reheapify
#Parent is greater than patient index then sift down
if patient_index != 0 and self.data[patient_index].priority < self.data[super()._parent_index(patient_index)].priority:
super()._sift_down(patient_index)
#Patient index is greater than parent then sift up
else:
super()._sift_up(patient_index)
def enqueue(self, patient):
""" Add a patient to the queue.
"""
assert isinstance(patient, Patient)
self.data.append(patient)
self.indices[patient.name] = len(self.data)-1
super()._sift_up(len(self.data)-1)
def dequeue(self):
""" Remove a patient from the front of the queue and return them.
"""
if len(self.data) == 0:
return None
elif len(self.data) == 1:
del self.indices[self.data[0].name]
return self.data.pop(0)
else:
patient = self.data[0]
self.data[0] = self.data[len(self.data)-1]
self.indices[patient.name] = 0
del self.indices[patient.name]
del self.data[len(self.data)-1]
super()._sift_down(0)
return patient
내 구현! 힙 불변 위반/AssertionError를 '제거'후 잘못된 힙 불변 : 부모 : 환자 (엘리자베스 전투, 2676) 어린이 : 환자 (Jonathan Bianchi, 63801)
도움이 될만한 의견이 있습니다.
항목을 대기열에 추가 할 때 'self.indices' 항목을 추가하지 않는 것 같습니다. –
안녕하세요, Jim, 정말 고마워요. 이제 builtins.KeyError 인 첫 번째 오류를 해결하는 데 도움이되는 enqueue 메서드에 다음 self.indices [patient.name] = len (self.data) -1을 추가했습니다. 'Juan Daudelin 'for patient_index = self.indices [patient_name] (remove 메소드에서). 하지만 난 아직도 두 번째 오류 builtins.KeyError : 환자 (로버트 로저스, 122209) 델 self.indices [환자]에 대한 dequeue 메서드를 받고있다. 이것이 일어날 수있는 이유에 대한 아이디어가 있습니까? 다시 한번 감사드립니다. – Turquoise25