우선 순위 대기열에서 임의의 요소 제거

Question

다음 작업에 대해 -이 작업의 경우 새 제거를 사용하여 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)

도움이 될만한 의견이 있습니다.

Answer 1

코드에 몇 가지 문제점이 있습니다.

첫 번째는 항목을 대기열에 추가 할 때 self.indices에 항목을 추가하지 않는다는 것입니다. 그래서 사전에서 환자 이름을 찾으려고 할 때, 거기에 있지 않습니다. 당신의 dequeue 방법에서

, 당신이 코드가 다음 elif 경우

elif len(self.data) == 1: 
     return self.data.pop() 
    else: 
     patient = self.data[0] 
     self.data[0] = self.data[len(self.data)-1] 
     del self.indices[patient] 
     del self.data[len(self.data)-1] 
     super()._sift_down(0) 
     return patient 

을, 당신은 self.indices에서 항목을 제거해야합니다.

else 사례에는 두 가지 문제점이 있습니다. 두 번째 줄에서는 힙 끝에있는 항목을 힙의 맨 위로 이동합니다. 좋습니다.하지만 사전에서 색인을 변경해야합니다. 이 줄을 추가하고 싶습니다.

self.indicies[self.data[0].patientName] = 0 

그렇지 않으면 해당 항목을 이동하려고 할 때 코드가 실패합니다.

삭제 오류 때문에 환자 이름 대신 환자가 indices 색인을 생성하려고합니다. 나는이 라인을 교체하는 게 좋을 것 : 당신의 remove 방법

del self.indices[patient.name] 

와

del self.indices[patient] 

을, 당신이 있습니다

#Remove the patient from the heap and dictionary 
    del self.data[end] 
    del self.indices[patient_name] 

    #Step 2: Reheapify 

당신은 항목의 경우 다음에 일어날 것을 고려할 수 있습니다 삭제중인 것은 힙의 마지막 항목입니다. patient_index은 self.data 끝에서부터 색인 생성됩니다.

디버거를 사용하여 중단 점을 추가하고 코드를 단계별로 수행하는 방법을 배우는 것이 좋습니다. 이를 통해 모든 데이터 구조의 상태를 볼 수 있습니다.예를 들어, dequeue 메서드를 단일 단계로 실행 한 경우 환자 이름이 사전에 대한 인덱스가 아닌 patient으로 전달된다는 것을 알았을 것입니다. 좋은 자료는 Eric Lippert의 How to debug small programs입니다.