HeapSort

HEAPSORT

O que é um HEAPSORT ?

O algoritmo HEAPSORT é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção. Foi desenvolvido em 1964 por Robert W. Floyd e J.W.J Williams; Foi desenvolvido com o objetivo de ser um

Ótimo ordenador de dados, tendo um consumo De memoria bastante reduzido;

Organizando dados por meio de Árvore Binaria ou HEAP.

Existem duas estruturas de HEAP a MAX-HEAP e MIN-HEAP;

MAX-HEAP e MIN-HEAP

A definição MAX-HEAP é utilizada quando no HEAP, o nó pai é sempre maior que qualquer um de seus filhos;

Em contrapartida, MIN-HEAP é utilizada quando no HEAP, o nó pai é sempre menor que qualquer um de seus filhos;

7

6 5

314 2

1

2 5

743 6Raiz: “Primeiro” ponto da arvore;Nó: Nó qualquer ponto;Nó Pai: Qualquer nó que tem 1 ou mais nó Filhos; Filhos: São as ramificações dos nós.

CONCLUINDO HEAP-SORT

De que forma um HEAP é utilizado para realizar uma operação de ordenação, se uma de suas características é justamente não ordenar os valores dos seus nós ?

Já que MAX-HEAP e MIN-HEAP, localiza o maior e menor valor respectivamente, logo, o mesmo é usado parar organizar valores em crescente e decrescente.

Uma vez que o MAX-HEAP é atendido, sua raiz é extraída, deixando de fazer parte da estrutura, e um novo MAX-HEAP é feito utilizando os nós restantes;

COMO SE MONTA A HEAP ?

QUAIS OS ÍNDICES?

9023 4 67 -8 54 21

S

E N

A I S P

Nó Pai= (i); Filho direito= 2i+1;Filho esquerdo= 2i+2;

i 0 1 2 3 4 5 6

0

Nó pai=(i)Nó pai=(0)

23


QUAIS OS ÍNDICES?

9023 4 67 -8 54 21


i 0 1 2 3 4 5 6

Filho direito= 2*0+1Filho direito= 1

Filho esquerdo= 2*0+2Filho esquerdo= 2

23

E N

A I S P

0

4 67

1 2


QUAIS OS ÍNDICES?

9023 4 67 -8 54 21


i 0 1 2 3 4 5 6



23

E N

A I S P

0

4 67

1 2


9023 4 67 -8 54 21


i 0 1 2 3 4 5 6


23

4 67

A I S P

01 2


9023 4 67 -8 54 21


i 0 1 2 3 4 5 6



3 4

23

4 67

A I S P

01 2

-8 90


9023 4 67 -8 54 21


i 0 1 2 3 4 5 6



3 4

23

4 67

A I S P

01 2

-8 90


9023 4 67 -8 54 21

23

4 67

-8 90 S P


i 0 1 2 3 4 5 6

0


12

3 4


9023 4 67 -8 54 21


i 0 1 2 3 4 5 6



23

4 67

-8 90 S P

01

2

3 4

54

5

21

6


9023 4 67 -8 54 21

23

4 67

-8 90 54 21


i 0 1 2 3 4 5 6

0


12

3 4 5 6


9023 4 67 -8 54 21


i 0 1 2 3 4 5 6



23

4 67

-8 90 S P

01

2

3 4

54

5

21

6

FILHOS SÃO MAIORES QUE O VETOR

HEAP ORGANIZADA

1ª FUNÇÃO PARA ORDENAR VALORES

void heapsort(int *vet, int N){int i, aux;

for(i=(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);

}}

1º for: Cria a Hip a partir dos dados no vetor.

2222º for: Pega o maior elemento da hip e coloca na posição corresponde no array.

Reconstrói a HIP




}



}}



Reconstrói a HIP




}



}}


IS E N A S Pi 0 1 2 3 4 5 6

i=(N-1)/2i=(7-1)/2

i=3

i=(N-1)/2

Números de elementos.Ponteiro do vetor.




}



}}


IS E N A S Pi 0 1 2 3 4 5 6

i=(N-1)/2i=(7-1)/2

i=3

i=(N-1)/2

Números de elementos.Ponteiro do vetor.




}



}}



Z Y X

Z

Y X

Pego o elemento que esta no topo da HIPE coloco numa variável auxiliar

Zaux

X

Coloco o valor de X no inicio e copio o valor de aux para o fim

Z




}



}}



Z Y X

Z

Y X

Pego o elemento que esta no topo da HIPE coloco numa variável auxiliar

Zaux

X

Coloco o valor de X no inicio e copio o valor de aux para o fim

Z




}



}}



Reconstrói a Heap

Esta Função é responsável por chamar a função criaHeap, a

qual vamos ver a seguir.


void criarHeap(int *vet, int i, int f){

int aux = vet[i];

int j = i * 2 + 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; i= 2 * i + 1; } else { j= f + 1; } }

vet[i] = aux;

}

Vetor.Inicio vetor.Final vetor.

Valor AUX = primeira posição do vetor (posição PAI).

Calculo de um dos Filhos.

Verifica se esta dentro do vetor.

Filho é menor que final do vetor?

Qual dos filhos é maior ? Atribui valor de J ao filho maior

Pai é menor que filho ?Se sim, filho se torna pai(pois o pai tem que ser maior que o filho)

E assim calcula o primeiro filho do mesmo

Z

Y XX

W

X



int aux = vet[i];

int j = i * 2 + 1;

while (j <= f){

if(j<f) {


} }


vet[i] = aux;

}






Qual dos filhos é maior ? Atribui valor de J ao filho maior

Pai é menor que filho ?Se sim, filho se torna pai(pois o pai tem que ser maior que o filho)

E assim calcula o primeiro filho do mesmo

Z

Y XX

W

X



int aux = vet[i];

int j = i * 2 + 1;

while (j <= f){

if(j<f) {


} }


vet[i] = aux;

}






Qual dos filhos é maior ? Atribui valor de J ao filho maior.

Pai é menor que filho ?Se não, atribui um valor para J maior que o vetor.

Antigo pai ocupa o lugar do ultimo filho analisado.

X

Y XX

W

XZ

HEAPSORT

NÁ PRÁTICA

23

4 67

-8 90 54 21

9023 4 67 -8 54 21

1º comando for: criaHeap(V, i, 6)Verifica qual elemento é maior

i 0 1 2 3 4 5 6

i=31 2

3

NA PRATICA!

i=(7-1)/2



}

i=(N-1)/2

NÃO TEM FILHOS

23

4 67

-8 90 54 21

i=21 2

3

23

4 67

-8 90 54 21

i=11 2

3

23

90 67

-8 4 54 21

i=01 2

3

0 0

0 0

-8

67PAI MAIOR QUE OS

FILHOS

4

90

FILHO MAIOR QUE O PAI, LOGO, OS DOIS

VALORES SÃO TROCADOS

23

90

FILHO MAIOR QUE O PAI, LOGO, OS DOIS

VALORES SÃO TROCADOS

NA PRATICA!for (i=N-1; i>=1; i--){ aux = vet[0]; vet[0]=vet[i]; vet[i]=aux; criaHeap(vet, 0, i-1); }

2º comando for: move maior elemento para o final e reorganiza o

restantei=N-1

490 23 67 -8 54 21i 0 1 2 3 4 5 6

90

23 67

-8 4 54 21

i=6

90

aux 21

23 67

-8 4 54 90


67

23 54

-8 4 21 90

21

90

67

21

467 23 54 -8 21 90i 0 1 2 3 4 5 6

90

54

21 90



restantei=N-1

i=5

67

aux


467 23 54 -8 21 90i 0 1 2 3 4 5 6

67

23 54

-8 4 21 90

21

23 54

-8 4 67 9067

54

21

54

23 21

-8 4 67 90

454 23 21 -8 67 90i 0 1 2 3 4 5 6

67

21

67



restantei=N-1

i=4

54

aux


54

23 21

-8 4 67 90

5423 4 21 -8 67 90i 0 1 2 3 4 5 6

4

23 21

-8 54 67 90

4

23

23

4 21

-8 54 67 90

454 23 21 -8 67 90i 0 1 2 3 4 5 6

54

4

5454



restantei=N-1

i=3

23

aux


5421 4 -8 23 67 90i 0 1 2 3 4 5 6

23

4 21

-8 54 67 90

-8

4 21

23 54 67 90

-8

21

21

4 -8

23 54 67 90

5423 4 21 -8 67 90i 0 1 2 3 4 5 6

-8

23

23

23



restantei=N-1

i=2

21

aux


5421 4 -8 23 67 90i 0 1 2 3 4 5 6

-8

4 21

23 54 67 90

21

4 -8

23 54 67 90

-8

4

4

-8 21

23 54 67 90

544 -8 21 23 67 90i 0 1 2 3 4 5 6

-8

21

21



restantei=N-1

i=1

4

aux


-8

4 21

23 54 67 90

4

-8 21

23 54 67 90

544 -8 21 23 67 90i 0 1 2 3 4 5 6

54-8 4 21 23 67 90i 0 1 2 3 4 5 6

-8

4 21

23 54 67 90

FIM DO FOR

-8

4

4

NA PRATICA!

54-8 4 21 23 67 90i 0 1 2 3 4 5 6

-8

4 21

23 54 67 90

ORDENADO

-8

IMAGENS ILUSTRADAS

GENÉRICO ESPECÍFICO

COMPARAÇÃO COM OUTROS ALGORITMOS

Valores iguais

Decrescente

Semi organizadas

Números aleatórios

CONSIDERAÇÕES FINAIS

Heapsort é bastante utilizado para controlar filas de prioridade. Podem ser filas de prioridades máximas ou filas de prioridades mínimas:

Filas de prioridades máximas: Um exemplo e a fila de trabalho em computadores compartilhados. Quando um trabalho termina ou é interrompido, o trabalho de prioridade mais alta é selecionado dentre os trabalhos pendentes. Filas de prioridades mínimas: Pode ser usado em um simulador de eventos, cada qual com um tempo de ocorrência, que serve como chaves. Os eventos devem ser simulados de acordo com o evento de ocorrência, porque a simulação de um evento pode provocar eventos futuros.


É recomendável para aplicações que não podem tolerar eventualmente um caso desfavorável.

Para dados imprevisíveis, pode ser mais vantajoso por ser previsível em termos de tempo de execução.

O anel interno do algoritmo é bastante complexo se comparado com o do quickSort.

Não é estável.

Construir a árvore-heap pode consumir muita memória.

Não é recomendado para arquivos com poucos registros , por causa do tempo necessário para construir o heap.VANTAGENS

DESVANTAGENS

RECOMENDADO PARA

Não é recomendado para arquivos com poucos registros, por causa do tempo necessário para construir o heap.

Para aplicações que não podem tolerar eventualmente um caso desfavorável.


Obrigado!Duvidas ?

Technology

HeapSort