Warum hört meine build_heap-Methode nicht auf zu laufen?

Question

Ich habe eine Klasse für eine MinHeap Klasse geschrieben und eine build_heap Methode erstellt. Immer wenn ich die build_heap Funktion anrufe, läuft das Programm weiter, es sei denn, ich werde von der Tastatur unterbrochen. Der Heap scheint aufgebaut zu sein, wenn ich den Funktionsaufruf abbringe, aber ich bin neugierig, warum die Funktion scheinbar unendlich läuft.

MinHeap Klasse:

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 

Ausgang beim Aufruf build_heap:

>>> 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

Das Problem perc_down() nie ist zurückkehrt, wenn build_help() es nennen. Dies liegt daran, dass sich die Bedingung (index * 2) <= self.current_size niemals ändert und immer True ist, da sie von keiner der Anweisungen innerhalb der while-Schleife betroffen ist.

Mit dem Wechsel und zusätzlich gezeigt, scheint es jetzt arbeiten:

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)