最小堆DecreaseKey函数两种实现是否等效？运行结果是否一致？

问题前提 #

DecreaseKey函数的入参为最小堆数组A、堆中节点索引i、待赋值的新值val，默认val不大于节点当前值，执行后需要恢复最小堆性质。

第一种实现 #

DecreaseKey(A, i, val)
    While (i > 1 and A[parent(i)] > val):
       A[i] = A[parent(i)]
       i = parent(i)
    A[i] = val

第二种实现 #

DecreaseKey(A, i, val)
    A[i] = val
    While (i > 1 and A[parent(i)] > A[i]):
       Swap(&A[i], &A[parent(i)])
       i = parent(i)

核心结论 #

• 两种实现逻辑都完全正确，不存在错误实现
• 对任意合法输入和任意最小堆，二者运行得到的最终堆结构完全一致，属于等价实现
• 仅实现细节和性能有差异：第一种是移位赋值实现，赋值操作次数更少，性能更优；第二种是交换实现，逻辑更直观，适合入门理解

具体说明 #

最小堆DecreaseKey的核心逻辑是统一的：节点值改小后，只要比父节点小就向上移动，直到满足父节点≤子节点的最小堆性质，或者到达根节点为止，两种实现都严格遵循该逻辑。

第一种实现提前暂存了最终要放入的val，循环过程中只把比val大的父节点值向下挪，找到最终位置后直接放val，每次循环只需要1次赋值操作，是《算法导论》中给出的标准工业实现。
第二种实现先把val写入节点，每次不符合堆性质就直接交换当前节点和父节点的值，每次交换底层需要3次赋值操作，性能略低，但代码逻辑更直白，更适合教学场景。

可以用简单示例验证一致性：假设初始堆为[0,2,3,4,5,6,7]（索引从1开始，根节点值为2），现在要把索引4的节点值5改为1，两种实现最终得到的堆都是[0,1,2,4,3,6,7]，没有任何差异。

内容的提问来源于stack exchange，提问作者mcr0yal