Compartilhe
Ver o tópico anteriorIr em baixoVer o tópico seguinte
avatar
Admin
Admin
Mensagens : 5
Pontos : 17
Reputação : 2
Data de inscrição : 05/05/2017
Idade : 27
Localização : Bandeirantes
Ver perfil do usuário

HeapSort - Método de Ordenação

em Seg Nov 13, 2017 2:51 pm
Definição
O HeapSort também conhecido como método de ordenação por arvores é baseado no método de seleção direta. Este algoritmo utiliza uma estrutura de dados chamada de heap, que consiste em uma arvore cuja raiz é o elemento de menor valor, caso seja um heap de mínimo, ou o de maior valor, caso seja um heap de máximo. Com o heap construído o HeapSort apenas cria o heap a partir do vetor de entrada, e o algoritmo apenas vai removendo do heap e colocando no vetor de saída.
A heap pode ser representada como uma árvore ou como um vetor, sendo ordenada de forma crescente e decrescente, desta forma, com a ordenação crescente deve ser construído um heap máximo (o maior elemento fica na raiz) onde A[i/2] >=A[i ] (ou seja, pai >= filho) (representação como árvore). Com a ordenação decrescente, deve ser construído um heap mínimo (o menor elemento fica na A [i/2] <=A [i ] (ou seja, pai <= filho) (representação como vetor).
Vantagens: O comportamento do Heapsort é sempre O(n log n), qualquer que seja a entrada. Não necessita de nenhuma memória adicional. E bom para arquivos com grandes registros. Desvantagens: O Heapsort não é recomendado para vetores de entrada com poucos elementos, devido a complexidade do heap; O Heapsort não é estável. O anel interno do algoritmo é bastante complexo se comparado com o do Quicksort.

Figura 1. Esquema de funcionamento do HeapSort

A figura mostra um vetor pq[1..55]. Os números dentro das caixas são os índices. O número de elementos em cada camada, exceto talvez no último, é uma potência de 2.  O pai de cada elemento na camada i está na camada i-1. O número de camadas é a parte inteira de 1+lg(55),  sendo lg(x) o piso de log2x.  Se eu tivesse N no lugar de 55, o número de camadas seria 1+lg(N).

Operações do Algoritmo

Função para Criar o Heap
Código:

void criaHeap (int *vet, int i, int f){
   int aux=vet[i];
   int j=2*i+1;
   while (j<=f){
       if(j<f){
            if(vet[j]<vet[j+1]) j=j+1;
       }
       if(aux<vet[j]){
             vet[i]=vet[j];
             i=j;
             j=2*1 + 1;
       }
       else j=f+1;
   }
   vet[i]=aux;
}

Função de Ordenação
Código:

void heapsort(int *vet, int N){
    int i, aux;
    for(i=(int) ((N-1)/2); i>=0; i--){
          criaHeap(vet, i, N-1);  
    }
    for(i=N-1; i>=1; i--){
          aux=vet[0];
          vet[0]=vet[i];
          vet[i]=aux;
          criaHeap(vet, 0, i-1);
    }
}

Videos para reforços ( ABRA OS SPOILERS )

HeapSort Método de Ordenação:



ATIVIDADE DE FIXAÇÃO ( ABRA O SPOILER )
Spoiler:

Clique "Questionário" para responder \/ :
Questionário
Ver o tópico anteriorVoltar ao TopoVer o tópico seguinte
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum