堆更新顺序

Question

这是堆排序算法的工作代码，我的问题是在堆创建过程中我是否将代码中的条件与

交换

for ( int i = 0 ; i  < dim/2-1; i ++)

我认为这是 for 循环，但顺序相反，我认为更新堆的过程是完全相同的（在我看来，我们通过更新每个索引的堆条件从 0 到结束数组），为什么算法不再有效？其他条件写错了，或者算法只是设计用于降低索引 i？谢谢

#include <stdio.h>

void Scambia( int *px, int *py);

void  Aggiornaheap( int *pa, int i, int j);

int main(void)
{
    int a[256];
    int n;
    int dim = 0;
    
    // Lettura dell’input da tastiera
    while (scanf("%d\n", &n) == 1)
    {
        a[dim] = n;
        dim++;
    }

    // heap creation
    for ( int i = dim/2-1 ; i  >= 0; i --)
    {
    Aggiornaheap(a, i, dim);
    }

    //Heapsort
    for ( int i = dim-1; i  >= 0; i --)
    {
    Scambia(&a[0], &a[i]);
    Aggiornaheap(a, 0, i-1);
    }

    for ( int i = 0; i < dim; i++)
        printf("%d ", a[i]);
    printf("\n");

return 0;
}

void Scambia( int *px, int *py)
{
    int temp;

    temp = *px;
    *px = *py;
    *py = temp;

}

void  Aggiornaheap( int *pa, int i, int j)
{
    int k;
    if ( 2*i == j )
    {
        if ( pa[i] < pa[j])
        Scambia(&pa[i], &pa[j]);
    }

    if ( 2*i < j )
    {
        if ( pa[2*i] > pa[2*i+1] )
            k = 2*i;
        else k = 2*i+1;
    
        if ( pa[i] < pa[k])
        {
            Scambia(&pa[i], &pa[k]);
            Aggiornaheap(pa, k, j);
        }
    }
}

Answer 1

必须以相反的顺序访问节点。如果您更改该顺序，算法将无法正确完成其工作。

以这个输入树为例，需要堆化成一个min-heap：[2,4,3,1]，可视化如下：

然后请注意，当您更改 for 循环以继续前进时，1 值不可能冒泡到顶部。让我们试试这个。当 i==0 时没有任何交换，因为 2 小于它的 children。当 i==1 时，4 将与 1 交换，然后循环结束。显然，这还没有创建有效的堆。

但是如果我们从 i==1 开始，这会触发 1 与 4 的交换，并且只有然后有 i==0，那么我们将再次交换1 个向上移动：

关于您的代码的一条评论。看起来您使用的是 zero-indexed 数组，根元素为 0，但在那种情况下 children 位于 i*2+1 和 i*2+2，一点也不像我们看到的那样在你的代码中。

堆更新顺序

Heap updating order

sorting

heap

heapsort