Heap Sort

 

O método de ordenação heap sort consiste numa árvore binária completa que obedece às seguintes propriedades:

§               Se o nó x é pai do nó y, então chave(x)>chave(y).

§               No último nível da árvore as folhas “são colocadas” em sequência, da esquerda para direita.

 

 

            A ordenação heap sort requer  apenas O(N * log(N)) operações sem dar importância à ordem de entrada.

 

 

 

 

 

Algoritmo Heapify (A, i)

 

l = esquerda(i)

r = direita(i)

 

Se (l £ heap_size(A)) e (A[l]>A[i])

Então largest = l

Senão largest = I

 

Se r £ heap_size(A) e A[r]>A[largest]

Então largest = r

Senão   Se largest i

             Então exchange (A[i], A[largest])

                        Heapify (A, largest)

 

 

 

Uma amostra da forma como se ordena o algoritmo haepify é o seguinte:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


1

15

10

4

12

9

3

2

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


15

1

10

4

12

9

3

2

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


15

12

10

4

1

9

3

2

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                No primeiro gráfico se pode observar que o primeiro nó não compre a propriedade de ser um heap, pois é menor que um dos seus filhos, por isso procura-se qual é o maior dos seus filhos e trocam-se  entre si. Logo, o nó trocado, tem de ser comparado com os seus novos filhos e se algum deles também é maior, então volta-se a fazer a troca pelo maior dos seus filhos, desta maneira basta que todos os nós cumpram as condições para formar um heap, ficando o final como no último gráfico.

 

            Depois disto, se deve iniciar o procedimento de BuildHeap, para o ordenamento dos dados. Os dados se vão ordenando de maneira inversa, primeiro se ordena o maior dos dados e se armazena no último lugar da fila, e assim sucessivamente até se localizar o menor dos elementos

 

 

Exemplos:

 

 

 

 

Implementação em C

 

typedef int element;

int tllH=0;

 

void heapify(int i) f

/* restaura a heap da sub-árvore de raiz i */

int l,r,maior;

element aux;

maior=i;

l=2*i;

r=2*i+1;

if ((l<=tllH) && (comp(v[l],v[i]) > 0)) maior=l;                  /* maior=argMax( */

   if ((r<=tllH) && (comp(v[r],v[maior]) > 0)) maior=r;       /* v[i],v[l],v[r]) */

      if (maior != i) f aux=v[maior];

          v[maior]=v[i]; v[i]=aux;    /* intercambio v[maior],v[i] */

      heapify(maior);

 

g g void buildHeap(int n) f

/* converte v[1..n] em Heap mediante heapify */

int i;

tllH=n;

for (i=(int )(n/2);

i>0;

i--) heapify(i);

g element extrMax() f

/* Extrai o elemento máximo do Heap (e  elimina-o) */

element x;

if (tllH==0) ERROR("**Erro: extrMax é uma heap vazia \n”);

x=v[1];

v[1]=v[tllH];

v[tllH]=x;     /* guarda o elemento extraído */

tllH--;

heapify(1);

return(x);    /* para uso futuro */

}