堆更新顺序

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

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

以需要堆化为最小堆的输入树为例：[2,4,3,1]，可以将其可视化如下：

            2
           / \
          4   3
         /
        1

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

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

            1
           / \
          2   3
         /
        4

关于您的代码的一条评论。看起来您使用的是零索引数组，根元素为 0，但在这种情况下，子元素位于 i*2+1 和 i*2+2 >，就像我们在您的代码中看到的那样。