なぜ私の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は決して変更されず、です。これは、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)