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") */ }