Fórum de discussão

Salve,

Alguns comentários sobre (max)heaps.

É mais simples dizer que um vetor v é um maxheap se

v[i/2] ≥ v[i]

para todo i que faz sentido (i = 2,3,...,n) em vez de

v[i] ≥ v[2×i] e v[i] ≥ v[2×i+1]

para todo i que faz sentido (hmmm, aqui fica mais enrolado escrever de maneira  precisa, pois temos que considerar dois caso 2×i ≤ n, 2×i+1 ≤ n, deixá para lá...)

Soluções para a primeira parte do exercício 12 da página Heapsort de Paulo Feofiloff.
Hmmm, o consumo de tempo das funções a seguir é O(lg n) mesmo?

/* Versao 1 */

void
ff (int n, int v[])
{
    int f =   n; /* filho */
    int p = f/2; /* pai de f */
    int x = v[n];

    while (p > 0 && v[p] < x) /* && nao é comutativo! */
    {
         v[f] = v[p]; /* copia conteudo do no pai para o filho */
         f    = p;   /* filho vira pai */
         p    = f/2; /* pai vira "avo" == pai de f */    
    }

    v[f] = x; 
}

/* Versao 2 */

void
ff (int n, int v[])
{
    int f; /* filho */
    int p; /* pai de f */
    int x = v[n];

    for (f = n, p = f/2; p > 0 && v[p] < x; f = p, p = f/2)
    {
         v[f] = v[p]; /* copia nó para filho */
    }

    v[f] = x; 
}

/* Versao 3: uma versao recursiva */

void
ff (int n, int v[])
{
    int x = v[n]; /* valor do no filho */

    /* primeiro a base */
    if (n == 1 || v[n/2] >= x) return;

    /* valor do no pai desce e o do filho sobe */
    v[n]  = v[n/2];
    v[n]    = x;
    ff(n/2, v);  /* recursao de cauda ("tail recursion") */
}