调整堆的具体代码
时间: 2023-07-03 17:21:21 浏览: 43
调整堆的具体代码如下:
```
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 的权重最小的子节点。如果当前节点只有一个子节点,则返回该子节点的索引;否则,返回左右子节点中权重最小的那个子节点的索引。