You need to enable JavaScript to run this app. Python构建最小堆统计交换索引的索引逻辑错误排查
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.10 06:51:00