Analise heapsort

-Heapsort:

Características:

*Ótimo ordenador de dados

*Consumo de memória reduzido

*Utiliza a técnica de estruturação de dados Heapsort

Heap

Uma fila de prioridades, tendo como base a árvore binária.

Características:

*Cada nó da árvore corresponde a um elemento do arranjo

*Árvore binária quase completa(exceção do último nível)

Propriedades do Heap:

A[PARENT(i)] >= a[i], condição precisa ser mantida

Manter essa condição através do HEAPFY, que é uma subrotina importante para

manipulação de um heap e tem duas entradas:

*Um arranjo A

*Um índice i

-Quando o HEAPFY é chamado, as sub-arvores da direita e esquerda são heaps

A[i] pode ser menor que seus filhos(violando o heap)

-HEAPFY forçará A[i]para posições inferiores da árvore, até que a propriedade

de heap seja re-estabelecida.

HEAPFY:

esquerda = left(i) = 2.i

direita = right(i) = 2.i + 1

m = importante

cond1 *se o tamanho de heap de A for menor que 1 e

A[1] > A[i] entao m = 1

cond2 *se tamanho do heap de A for menor que r e

A[r] for maior que A[m] então m= re-estabelecida

cond3: if m for diferente de i

Obs: o HEAPFY tem que começar com (A, 2) para poder iniciar o

processo do heap( porque o 1 elemnto é a raiz).

Ex:

Lista

16, 4, 10, 14, 7, 9, 3, 2,8, 1( vetor A de 10 posições)

1) Passo

Inicia o heapy(A,2) // vetor A de posições, 2 = filho da esquerda

l = left(i) // left(2.i)

r = right(i) //right(i) = 2.i + 1

m = i

então:

i = 4 ( posição 2 do vetor A)

2) Passo

if l < tam-heap(A) && A[l] > A[i] // se a condição for verdadeira então

m = l

então:

m, i = 4 ( posição 2 do vetor A)

l = 14 ( posição 4 do vetor A, filho esquerdo da posição 2)

r = 7 (posição 5 do vetor A, filho direito da posição 2)

3) Passo

if r <=tam-heap(A) && A[r] > A[m]// Se a condição for verdadeira então

m = r

Então:

i = 4 ( posição 2 do vetor A)

m = 14 ( posição 4 do vetor A, filho esquerdo da posição 2)

l = 14 ( posição 4 do vetor A, filho esquerdo da posição 2)

r = 7 (posição 5 do vetor A, filho direito da posição 2)

4) Passo

if m != i { // se condição verdadeira então

trocar(A[i],A[m]);

HEAPFY(A,m);

}

Então:

i = 14 ( posição 2 do vetor A, filho esquerdo da raiz)

m = 4 ( posição 4 do vetor A, filho esquerdo da posição 2)

l = 4 ( posição 4 do vetor A, filho esquerdo da posição 2)

r = 7 (posição 5 do vetor A, filho direito da posição 2)

Fim

OBSERVAÇÃO:

Depois da