왜 내 build_heap 메서드가 실행을 멈추지 않을까요?

Question

MinHeap 클래스의 클래스를 작성하고 build_heap 메소드를 작성했습니다. build_heap 함수를 호출 할 때마다 키보드가 인터럽트되지 않으면 프로그램이 계속 실행됩니다. 힙은 함수 호출을 중단 할 때 생성 된 것처럼 보이지만 함수가 무한대로 실행되는 이유에 대해 궁금합니다.

MinHeap 등급 :

class MinHeap: 
    def __init__(self): 
     self.heap_list = [0] 
     self.current_size = 0 

    def perc_up(self, index): 
     while index // 2 > 0: 
      if self.heap_list[index] < self.heap_list[index // 2]: 
       temp = self.heap_list[index // 2] 
       self.heap_list[index // 2] = self.heap_list[index] 
       self.heap_list[index] = temp 
      index = index // 2 

    def perc_down(self, index): 
     while (index * 2) <= self.current_size: 
      mc = self.min_child(index) 
      if self.heap_list[index] > self.heap_list[mc]: 
       temp = self.heap_list[index] 
       self.heap_list[index] = self.heap_list[mc] 
       self.heap_list[mc] = temp 
      i = mc 

    def min_child(self, index): 
     if (index * 2 + 1) > self.current_size: 
      return index * 2 
     else: 
      if self.heap_list[index * 2] < self.heap_list[index * 2 + 1]: 
       return index * 2 
      else: 
       return index * 2 + 1 

    def insert(self, value): 
     self.heap_list.append(value) 
     self.current_size += 1 
     self.perc_up(self.current_size) 

    def peek(self): 
     return self.heap_list[1] 

    def del_min(self): 
     ret_val = self.heap_list[1] 
     self.heap_list[1] = self.heap_list[self.current_size] 
     self.heap_list.pop() 
     self.perc_down(1) 
     return ret_val 

    def is_empty(self): 
     if self.current_size == 0: 
      return True 
     else: 
      return False 

    def size(self): 
     return self.current_size 

    def build_heap(self, a_list): 
     i = len(a_list) // 2 
     self.current_size = len(a_list) 
     self.heap_list = [0] + a_list[:] 
     while (i > 0): 
      self.perc_down(i) 
      i = i - 1 

출력 build_heap 전화 : build_help() 그것을 호출 할 때 문제가 perc_down()입니다

>>> heap = MinHeap() 
>>> lyst = [ 1, 3, 6, 19, 13, 4, 2] 
>>> heap.build_heap(lyst) 

Traceback (most recent call last): 
    File "<pyshell#13>", line 1, in <module> 
    heap.build_heap(lyst) 
    File "C:/Users/frost_000/Documents/Python Files/MinHeap.py", line 62, in   build_heap 
self.perc_down(i) 
    File "C:/Users/frost_000/Documents/Python Files/MinHeap.py", line 16, in perc_down 
    while (index * 2) <= self.current_size: 
KeyboardInterrupt 

>>> heap.heap_list 
>>> [0, 1, 3, 2, 19, 13, 4, 6] 

Answer 1

는 결코 반환하지 않습니다. 이는 (index * 2) <= self.current_size 조건이 변경되지 않으며 항상 True이므로 루프가 while 루프 내에있는 명령문의 영향을받지 않기 때문에 항상 적용됩니다.

class MinHeap: 
    def __init__(self): 
     self.heap_list = [0] 
     self.current_size = 0 

    def perc_up(self, index): 
     while index // 2 > 0: 
      if self.heap_list[index] < self.heap_list[index // 2]: 
       temp = self.heap_list[index // 2] 
       self.heap_list[index // 2] = self.heap_list[index] 
       self.heap_list[index] = temp 
      index = index // 2 

    def perc_down(self, index): 
     while (index * 2) <= self.current_size: 
      mc = self.min_child(index) 
      if self.heap_list[index] > self.heap_list[mc]: 
       temp = self.heap_list[index] 
       self.heap_list[index] = self.heap_list[mc] 
       self.heap_list[mc] = temp 
      index = mc #### changed 

    def min_child(self, index): 
     if (index * 2 + 1) > self.current_size: 
      return index * 2 
     else: 
      if self.heap_list[index * 2] < self.heap_list[index * 2 + 1]: 
       return index * 2 
      else: 
       return index * 2 + 1 

    def insert(self, value): 
     self.heap_list.append(value) 
     self.current_size += 1 
     self.perc_up(self.current_size) 

    def peek(self): 
     return self.heap_list[1] 

    def del_min(self): 
     ret_val = self.heap_list[1] 
     self.heap_list[1] = self.heap_list[self.current_size] 
     self.heap_list.pop() 
     self.current_size -= 1 #### added 
     self.perc_down(1) 
     return ret_val 

    def is_empty(self): 
     if self.current_size == 0: 
      return True 
     else: 
      return False 

    def size(self): 
     return self.current_size 

    def build_heap(self, a_list): 
     i = len(a_list) // 2 
     self.current_size = len(a_list) 
     self.heap_list = [0] + a_list[:] 
     while (i > 0): 
      print('i: {}'.format(i)) 
      self.perc_down(i) 
      i = i - 1 

heap = MinHeap() 
lyst = [ 1, 3, 6, 19, 13, 4, 2] 
heap.build_heap(lyst)