이 힙 구현은 무엇이 문제입니까?

Question

내 삽입 방법이 올바르지 않아 이유를 모르겠습니다. "builtin_function 또는 object가 subscriptable이 아닌"내 min 메소드 오류 "

힙에 대한 개념적 이해가 좋다고 생각합니다. 그러나 좌절의 파쇄가 insert에

class Heap: 
    def __init__(self): 
     self.array = [] 

    def find_children(self, index): 
     """ return both the left and right children """ 
     return index * 2 + 1, index * 2 + 2 

    def insert(self, value): 
     """ append node value to the array, then bubble up 
     to its rightful place 
     """ 
     self.array.append(value) 
     index = self.array.index(value) 

     while index > 0 or self.array[index] < self.array[index // 2 - 1]: 
      if self.array[index] < self.array[index // 2 - 1]: 
       temp = self.array[index] 
       self.array[index] = self.array[index // 2 - 1] 
       self.array[index // 2 - 1] = temp 
      index = index // 2 - 1 

    def min(self): 
     """ remove the min at the root, then bubble down to 
     maintain heap property 
     """ 
     minimum = self.array[0] 
     self.array[0] = self.array[-1] 
     self.array.pop() 

     index = self.array.index[minimum] 

     while index <= len(self.array): 
      leftChildIndex, rightChildIndex = self.find_children(index) 
      minChild = min(self.array[leftChildIndex], self.array[rightChildIndex]) 
      if self.array[index] > minChild: 
       temp = self.array[index] 
       self.array[index] = minChild 
       minChild = temp 
      index = minChild 

     return minimum 

    def p(self): 
     return self.array 

Answer 1

:(라인 self.array.index(value)을 내려 쓸 때 실제로는 위험하다. 무엇 이미 힙에 존재하는 값의 삽입을한다면? 당신은 (대신을 len(self.array)을 사용해야 발생 ') 배열에 추가 다시, 그래서 마지막 요소가 될 것입니다. 마찬가지로

, min에 효과적으로 동일 않습니다. 당신은 그 인덱스를 검색 할 필요가 없습니다, 당신은 이미 그것을 알고있다.

아마도 실제로는 자신의 "leng th "및"capacity "속성을 사용하는 것이 좋습니다. 백업 배열을 확장하거나 축소하면 예상되는 모든 로그 (n)가 손상됩니다.