构建min-heap的Python实现

Question

下面的代码构建最小堆有什么问题？bubble-up方法不起作用，它会得到一个索引超出范围的错误。在

 def __init__(self):
    self.heap = []
    self.heap_size = 0

 def bubble_up(self, i):
    print(self.heap)
    while i // 2 > 0:
        if self.heap[i] < self.heap[i // 2]:
            tmp = self.heap[i // 2 - 1]
            self.heap[i] = self.heap[i // 2]
            self.heap[i // 2] = tmp
        print(self.heap)
        i = i // 2


def insert(self, data):
    self.heap.append(data)
    self.heap_size = self.heap_size + 1
    self.bubble_up(self.heap_size)

if __name__ == "__main__":
    min_heap = MinHeap()
    min_heap.insert(5)
    min_heap.insert(4)
    min_heap.insert(3)
    min_heap.insert(2)
    min_heap.insert(6)

Answer 1

def insert(self, data):
    self.heap.append(data)
    self.heap_size = self.heap_size + 1
    self.bubble_up(self.heap_size)

您可以附加数据，增加heap_size，然后使用新的（增加的）堆大小调用您的bubble_up。在

在那里，你可以检查：

^{pr2}$

其中i是堆大小。不能这样做，如果堆中有3个元素，则无法访问heap[3]。它不存在，您唯一有效的索引是0, 1, 2。在

可能的修复（未测试）：用heap_size - 1调用bubble_up。在

请注意，if中的代码看起来并不正确：

tmp = self.heap[i // 2 - 1]        # why -1 here? shouldn't this be heap[i]?
self.heap[i] = self.heap[i // 2]   # shouldn't this be the other way around? why no -1 here?
self.heap[i // 2] = tmp            # why no -1 here? shouldn't this be heap[i]?

另外，您可以将i // 2放入该条件中，如果条件为false，则中断循环。在

Answer 2

当前发布的答案准确地描述了为什么会出现越界错误，但是如果只使用heap_size-1调用bubble_up()，它将无法正确维护堆。请注意bubble_up()中代码的以下部分：

while i // 2 > 0:

当前的while循环语句不会将堆根的立即子级与根级的子级进行比较。假设您插入3，然后插入1。当您插入1时，bubble_up()将不能正确地将插入的1与3交换，因为它不会在while语句中运行swap例程，因为i//2 == 0是插入到1的位置。我会把这个街区换成：

^{pr2}$