【勘误】关于从0开始索引的堆最后一个非叶子结点索引值的计算

Question

在这一小节，我们创建的堆开始使用从0开始索引的数组，而非从1开始索引。所以之前介绍的一些基本计算也要发生相应的改变。非常抱歉大家，其中最后一个非叶子节点的索引计算，我在课程中的PPT给出的计算公式是错误的。不应该是（count-1）/2，而应该是（最后一个元素索引值-1）/2。在从0开始索引的数组中，最后一个元素的索引值为count-1，所以最后一个非叶子节点的索引值就应该是 (count-1-1)/2 = (count-2)/2。

有意思的是，虽然在课程中讲解的这步计算时错误的，但我们写出的堆排序算法确是正确的，这是为什么呢。这是因为我的错误计算方式，有可能找到的是第一个叶子节点。按照我们的逻辑，就会针对这个叶子节点进行ShiftDown操作。但是叶子节点没有子节点，ShiftDown操作直接结束了。下面就会真正作用在第一个非叶子结点上。也就是我们的计算方式，有可能让我们的堆排序算法多运行一步。这一步对效率的影响也是微乎其微的。真是非常巧合的错误啊：）

再次抱歉大家。修改后的代码见下。这个课程的官方github代码也已经进行了更新。可参见：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/04-Heap/Course%20Code%20(C%2B%2B)/06-Heap-Sort/main.cpp

template<typename T>    
void heapSort(T arr[], int n){    

    // 从(最后一个元素的索引-1)/2开始    
    // 最后一个元素的索引 = n-1    
    for( int i = (n-1-1)/2 ; i >= 0 ; i -- )    
        __shiftDown2(arr, n, i);    
    
    for( int i = n-1; i > 0 ; i-- ){    
        swap( arr[0] , arr[i] );    
        __shiftDown2(arr, i, 0);    
    }    
}

Answer 1

缱绻091 2020-02-01 10:43:51

这个地方确实容易混淆

Answer 2

LittleWorker 2019-12-14 11:08:21

这里我想了半天，怎么都觉得是(索引-1/2)。果然是这样啊

Answer 3

苏丛JS 2019-08-11 13:59:59

哈哈正想问这个, 有两次偏移, 一次是最后一个叶子节点, 一次是最后一个非叶子节点