下面的代码构建最小堆有什么问题?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)
您可以附加数据,增加
heap_size
,然后使用新的(增加的)堆大小调用您的bubble_up
。在在那里,你可以检查:
^{pr2}$其中
i
是堆大小。不能这样做,如果堆中有3
个元素,则无法访问heap[3]
。它不存在,您唯一有效的索引是0, 1, 2
。在可能的修复(未测试):用
heap_size - 1
调用bubble_up
。在请注意,
if
中的代码看起来并不正确:另外,您可以将
i // 2
放入该条件中,如果条件为false,则中断循环。在当前发布的答案准确地描述了为什么会出现越界错误,但是如果只使用
heap_size-1
调用bubble_up()
,它将无法正确维护堆。请注意bubble_up()
中代码的以下部分:当前的while循环语句不会将堆根的立即子级与根级的子级进行比较。假设您插入
^{pr2}$3
,然后插入1
。当您插入1
时,bubble_up()
将不能正确地将插入的1与3交换,因为它不会在while语句中运行swap例程,因为i//2 == 0
是插入到1
的位置。我会把这个街区换成:相关问题 更多 >
编程相关推荐