为什么我的 build_heap 方法不会停止运行？

Question

我为 MinHeap class 编写了 class 并创建了 build_heap 方法。每当我调用 build_heap 函数时，程序都会继续运行除非我用键盘打断它。当我中断函数调用时，堆似乎已建立，但我很好奇为什么函数似乎是运行ning 无限。

最小堆Class:

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时的输出：

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

问题是 perc_down() 在 build_help() 调用它时从未 returns。这是因为条件 (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)

为什么我的 build_heap 方法不会停止运行？

Why will my build_heap method not stop running?

python

heap

interrupt

为什么我的 build_heap 方法不会停止 运行？

Why will my build_heap method not stop running?

python

heap

interrupt

为什么我的 build_heap 方法不会停止运行？