修改代码 while (i * 2) <= self.currentSize: mc = self.minChild(i) if mc <=0: break if self.heapArray[i][0] > self.heapArray[mc][0]: tmp = self.heapArray[i] self.heapArray[i] = self.heapArray[mc] self.heapArray[mc] = tmp i = mc
时间: 2024-02-14 18:05:15 浏览: 24
根据代码的缩进,可以看出这是堆排序中的“下滤”操作。现在代码中的 while 循环条件是判断当前节点 i 是否有子节点,但是这个条件可能会导致无限循环,因为 i 的值不会改变,所以需要修改循环条件。
建议修改为:
```
while i * 2 <= self.currentSize:
mc = self.minChild(i)
if mc <= 0:
break
if self.heapArray[i][0] > self.heapArray[mc][0]:
tmp = self.heapArray[i]
self.heapArray[i] = self.heapArray[mc]
self.heapArray[mc] = tmp
i = mc
```
这样,每次循环结束后都会将 i 的值更新为下一层的节点,从而避免无限循环的问题。
相关问题
def percDown(self, i): while (i * 2) <= self.currentSize: mc = self.minChild(i) if mc <=0: break if self.heapArray[i][0] > self.heapArray[mc][0]: self.heapArray[i], self.heapArray[mc] = self.heapArray[mc], self.heapArray[i] i = mc有问题吗
这段代码是堆排序中的“下滤”操作,用于保证堆的性质。代码看起来没有问题,但是建议将第 4 行的条件修改为 mc < 0,因为当前节点的索引 i 是大于等于 1 的,如果 mc 小于等于 0,则说明当前节点 i 没有子节点了,这种情况下应该退出循环。
修改后的代码如下:
```
def percDown(self, i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if mc < 0:
break
if self.heapArray[i][0] > self.heapArray[mc][0]:
self.heapArray[i], self.heapArray[mc] = self.heapArray[mc], self.heapArray[i]
i = mc
```
这样修改之后,代码更加严谨,可以避免出现不必要的循环。
def percDown(self, i): while (i * 2) <= self.currentSize: mc = self.minChild(i) if mc < 0: break if self.heapArray[i][0] > self.heapArray[mc][0]: self.heapArray[i], self.heapArray[mc] = self.heapArray[mc], self.heapArray[i] i = mc def minChild(self, i): if i * 2 > self.currentSize: return -1 else: if i * 2 + 1 > self.currentSize: return i * 2 else: if self.heapArray[i * 2-1][0] < self.heapArray[i * 2][0]: # 修改 return i * 2 else: return i * 2 + 1i = len(alist) // 2 while (i > 0): pq.percDown(i) i = i - 1查找错误并修改
在minChild函数中,第7行代码需要修改为`if self.heapArray[i * 2][0] < self.heapArray[i * 2 + 1][0]:`,因为原代码中比较的是`self.heapArray[i * 2-1][0]`和`self.heapArray[i * 2][0]`,但是这是错误的,应该比较的是左右子节点的大小。修改后的代码如下:
```
def percDown(self, i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if mc < 0:
break
if self.heapArray[i][0] > self.heapArray[mc][0]:
self.heapArray[i], self.heapArray[mc] = self.heapArray[mc], self.heapArray[i]
i = mc
def minChild(self, i):
if i * 2 > self.currentSize:
return -1
else:
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapArray[i * 2][0] < self.heapArray[i * 2 + 1][0]: # 修改
return i * 2
else:
return i * 2 + 1
i = len(alist) // 2
while (i > 0):
pq.percDown(i)
i = i - 1
```