python - 构建最小堆的Python实现

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

 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)

最佳答案

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

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

关于python - 构建最小堆的Python实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29755845/