COS-121

Estrutura de Dados e Algoritmos

2º Semestre de 2014

 Professor Ricardo Farias

Aula 09

Tópicos desta aula.

Linguagem C

Ordenação dos Elementos de um Vetor


Heap Sort

O heapsort utiliza uma estrutura de dados chamada heap binário para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada.

Um heap binário é uma árvore binária mantida na forma de um vetor.

0 1 2 3 4 5 6
40 90 20 10 50 70 80

O heap é gerado e mantido no próprio vetor a ser ordenado.

Para uma ordenação crescente, deve ser construído um heap máximo (o maior elemento fica na raiz). Para uma ordenação decrescente, deve ser construído um heap mínimo (o menor elemento fica na raiz).

Veja o exemplo:

Observe a figura: As subárvores são analisadas e o maior elemento da subárvore é colocado na raiz.

0 1 2 3 4 5 6
40 90 20 10 50 70 80
0 1 2 3 4 5 6
40 90 80 10 50 70 20

No nível acima.

0 1 2 3 4 5 6
40 90 80 10 50 70 20
0 1 2 3 4 5 6
90 40 80 10 50 70 20

Quando há troca num nó pai, suas subárvores são analisadas novamente.
0 1 2 3 4 5 6
90 40 80 10 50 70 20
0 1 2 3 4 5 6
90 50 80 10 40 70 20


Observe, na figura acima, que cada uma das raízes possui o maior elemento das suas respectivas subárvores. Agora a raiz será trocada com o elemento da última posição.
0 1 2 3 4 5 6
90 50 80 10 40 70 20
0 1 2 3 4 5 6
20 50 80 10 40 70 90

O resultado é que o maior elemento foi colocado na última posição do vetor:

0 1 2 3 4 5 6
20 50 80 10 40 70 90
O processo reinicia: os nodos são reavaliados de forma a colocar o maior elemento de cada subárvore na respectva raiz (a última posição fica de fora, agora).
0 1 2 3 4 5 6
20 50 80 10 40 70 90
0 1 2 3 4 5 6
80 50 20 10 40 70 90

0 1 2 3 4 5 6
80 50 20 10 40 70 90
0 1 2 3 4 5 6
80 50 70 10 40 20 90

0 1 2 3 4 5 6
80 50 70 10 40 20 90
0 1 2 3 4 5 6
80 50 70 10 40 20 90

Resultado:

E o processo continua:
0 1 2 3 4 5 6
20 50 70 10 40 80 90
0 1 2 3 4 5 6
70 50 20 10 40 80 90

0 1 2 3 4 5 6
20 50 70 10 40 80 90
0 1 2 3 4 5 6
70 50 20 10 40 80 90

0 1 2 3 4 5 6
40 50 20 10 70 80 90

0 1 2 3 4 5 6
40 50 20 10 70 80 90
0 1 2 3 4 5 6
50 40 20 10 70 80 90

0 1 2 3 4 5 6
50 40 20 10 70 80 90
0 1 2 3 4 5 6
10 40 20 50 70 80 90

0 1 2 3 4 5 6
10 40 20 50 70 80 90

0 1 2 3 4 5 6
10 40 20 50 70 80 90
0 1 2 3 4 5 6
40 10 20 50 70 80 90

0 1 2 3 4 5 6
40 10 20 50 70 80 90
0 1 2 3 4 5 6
20 10 40 50 70 80 90

0 1 2 3 4 5 6
20 10 40 50 70 80 90

0 1 2 3 4 5 6
20 10 40 50 70 80 90
0 1 2 3 4 5 6
10 20 40 50 70 80 90

0 1 2 3 4 5 6
10 20 40 50 70 80 90

O processo de ordenação termina!

Veja o algoritmo a seguir: 

#include 
#include 

void lerVet( int *p, int t ){

	int i;

	for ( i=0; i 0 ) {

          i--;
          t = a[i];

      }
      else {

          n--;
          if (n == 0)
             return;

          t = a[n];
          a[n] = a[0];

      }
     
      pai = i;
      filho = i*2 + 1;
 
      while (filho < n) {

          if (( filho + 1 < n )  &&  ( a[filho + 1] > a[filho] ))
              filho++;

          if (a[filho] > t) {

             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;

          }
          else
             break;

      }
      a[pai] = t;

   }
}


int main(){

	int *p, tam;

	printf("Quantidade de elementos do vetor? ");
	scanf("%d",&tam);

	p = (int*) malloc(tam * sizeof(int));
	
	printf("\nDigite o conteudo do vetor:\n");
	lerVet(p, tam);

	printf("\nConteudo digitado para o vetor:\n");
	mostrarVet(p, tam);

	printf("\nOrdenando o vetor...\n");
	heapSort(p, tam);

	printf("\nConteudo do vetor ja ordenado:\n");
	mostrarVet(p, tam);

	free(p);

	return 0;

}

Que alterações devem ser realizadas no algoritmo para que o vetor seja ordenado decrescentemente?