Python构建最小堆统计交换索引的索引逻辑错误排查
最小堆构建及交换索引记录问题排查
错误原因
你的代码存在3处核心逻辑错误:
- 堆初始化遍历的起始索引错误:长度为
n的数组,最后一个非叶子节点的索引为n//2 - 1,原代码直接从n//2开始遍历,多处理了一个无有效子节点的索引,漏掉了正确的非叶子节点遍历。 - 下沉逻辑未做子节点存在性校验:当节点只有左子节点、无右子节点时,直接访问
a[right]会触发索引越界,原代码未做边界判断。 - 子节点最小值判断逻辑不严谨:原代码直接通过父节点和左右子节点的大小比较触发交换,未先定位最小子节点的位置,逻辑容错性低。
修正后代码
def mins(a, i, res): n = len(a) smallest = i # 记录当前最小值对应的索引,默认是当前父节点 left = 2 * i + 1 right = 2 * i + 2 # 校验左子节点存在,且值更小 if left < n and a[left] < a[smallest]: smallest = left # 校验右子节点存在,且值更小 if right < n and a[right] < a[smallest]: smallest = right # 最小值不是父节点时执行交换,继续下沉 if smallest != i: res.append([i, smallest]) a[i], a[smallest] = a[smallest], a[i] mins(a, smallest, res) def heapify(a, res): n = len(a) # 从最后一个非叶子节点倒序遍历做下沉 for i in range(n//2 - 1, -1, -1): mins(a, i, res) return res # 测试用例 a = [7, 6, 5, 4, 3, 2] res = heapify(a, []) print(a) print(res)
输出说明
运行上述代码后:
- 交换索引
res的输出为[[2, 5], [1, 4], [0, 2], [2, 5]],和你的预期完全一致 - 堆数组输出为
[2, 3, 5, 4, 6, 7],符合最小堆的定义(所有父节点值小于等于子节点值)。你预期的[2, 3, 4, 5, 6, 7]是堆排序完成后的全有序结果,不是最小堆构建完成的原生状态,若需要全有序数组,可在堆构建完成后追加堆排序的弹出逻辑。
内容的提问来源于stack exchange,提问作者Ramiil
相关产品推荐
相关产品推荐

