构建min heap的Python实现

Question

下面的代码构建一个最小堆有什么问题？冒泡方法不起作用，它会导致索引超出范围错误。

 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。

在那里，你检查：

 if self.heap[i] < self.heap[i // 2]:

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

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

请注意，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

当前的答案准确地描述了为什么你得到一个outofbounds错误，但如果你只是用bubble_up()调用heap_size-1，它将无法正确维护堆。请注意bubble_up()中代码的以下部分：

while i // 2 > 0:

您当前的while循环语句不会将堆根的直接子节点与根节点进行比较。假设您插入3然后1。当你插入1时，bubble_up()将无法正确地将插入的1与3交换，因为由于i//2 == 0插入位置i == 1，因此1将不会在你的while语句中运行交换例程。我将此块切换为以下内容：

while i > 0:
    parent = i // 2
    <put your comparison & swap method here>
    i = parent