minChild代码
时间: 2023-07-03 18:21:21 浏览: 38
以下是 minChild 方法的具体代码:
```
def minChild(self, i):
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 是否有右子节点。如果没有右子节点,则返回左子节点的索引 i * 2。否则,比较左右子节点的权重,返回权重最小的子节点的索引,如果左右子节点的权重相等,任意返回一个子节点的索引即可。
相关问题
percDown 代码
以下是 percDown 方法的具体代码:
```
def percDown(self, i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
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
```
在该方法中,我们通过 while 循环向下遍历堆的子节点。首先,我们使用 minChild 方法找到当前节点 i 的权重最小的子节点 mc。然后,如果当前节点的权重比 mc 的权重大,则交换两个节点的位置,将当前节点指向 mc,继续向下遍历。如果当前节点的权重已经小于等于 mc 的权重,则停止向下遍历。
调整堆的具体代码
调整堆的具体代码如下:
```
def percUp(self, i):
while i // 2 > 0:
if self.heapArray[i][0] < self.heapArray[i // 2][0]:
tmp = self.heapArray[i // 2]
self.heapArray[i // 2] = self.heapArray[i]
self.heapArray[i] = tmp
i = i // 2
def percDown(self, i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
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
def minChild(self, i):
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
```
其中,percUp 方法用于向上调整堆的结构,使其满足最小堆的性质。具体来说,它从当前节点 i 开始,向上遍历堆的父节点,如果父节点的权重比当前节点的权重大,则交换两个节点的位置,然后将当前节点指向父节点,继续向上遍历,直到堆的根节点为止。
percDown 方法用于向下调整堆的结构,使其满足最小堆的性质。具体来说,它从当前节点 i 开始,向下遍历堆的子节点,找到权重最小的子节点 mc,如果 mc 的权重比当前节点的权重小,则交换两个节点的位置,然后将当前节点指向 mc,继续向下遍历,直到堆的最后一个非叶子节点为止。
minChild 方法用于找到当前节点 i 的权重最小的子节点。如果当前节点只有一个子节点,则返回该子节点的索引;否则,返回左右子节点中权重最小的那个子节点的索引。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)