Heap updating order-CodePudding

here's a working code for heapsort algorithm, my question is if in heap creation I swap the condition in the code with

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

that I think it's the for cycle but in reverse order and I think that the process of updating the heap is quite the same (in my head we go trough updating the heap condition for every index from 0 to the end of the array),why the algorithm won't work anymore? It's wrong written the other condition or simply the algorithm is designed to work decreasing the index i? Thank you

#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);
        }
    }
}

CodePudding user response：

It is necessary that the nodes are visited in reverse order. The algorithm will not do its job correctly if you change that order.

Take for instance this input tree that needs to be heapified into a min-heap: [2,4,3,1], which can be visualised as follows:

Then note how it will be impossible for the 1 value to bubble to the top, when you alter the for loop to go forward. Let's just try this. When i==0 nothing is swapped, because 2 is less than its children. When i==1 then 4 will be swapped with 1, and then the loop has finished. Clearly, this has not created a valid heap.

If however we start with i==1, which triggers the swap of 1 with 4, and only then have i==0, then we will again swap 1 to move up:

One comment about your code. It looks like you work with zero-indexed arrays, with the root element at 0, but in that case the children are at i*2 1 and i*2 2, not one less like we see in your code.