HeapSort

Explicação algoritmo de Heapsort, contendo animações passo a passo de como funciona o mesmo, contendo também vantagens e desvantagens e comparações com outros algoritmos de ordenação

1. HEAPSORT

2. 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 ;

3. 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 3 1 4 2 1 2 5 7 4 3 6 Raiz: “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.

4. 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;

5. COMO SE MONTA A HEAP ? QUAIS OS ÍNDICES? 90 23 4 67 -8 54 21 S E N A I S P Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Nó pai=(i) Nó pai=(0) 23

6. COMO SE MONTA A HEAP ? QUAIS OS ÍNDICES? 90 23 4 67 -8 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Filho direito= 2*0+1 Filho direito= 1 Filho esquerdo= 2*0+2 Filho esquerdo= 2 23 E N A I S P 4 67 1 2

7. COMO SE MONTA A HEAP ? QUAIS OS ÍNDICES? 90 23 4 67 -8 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Filho direito= 2*0+1 Filho direito= 1 Filho esquerdo= 2*0+2 Filho esquerdo= 2 23 E N A I S P 4 67 1 2

8. COMO SE MONTA A HEAP ? 90 23 4 67 -8 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Nó pai=(i) Nó pai=(1) 23 4 67 A I S P 1 2

9. COMO SE MONTA A HEAP ? 90 23 4 67 -8 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Filho direito= 2*1+1 Filho direito= 3 Filho esquerdo= 2*1+2 Filho esquerdo= 4 3 4 23 4 67 A I S P 1 2 -8 90

10. COMO SE MONTA A HEAP ? 90 23 4 67 -8 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Filho direito= 2*1+1 Filho direito= 3 Filho esquerdo= 2*1+2 Filho esquerdo= 4 3 4 23 4 67 A I S P 1 2 -8 90

11. COMO SE MONTA A HEAP ? 90 23 4 67 -8 54 21 23 4 67 -8 90 S P Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Nó pai=(i) Nó pai=(2) 1 2 3 4

12. COMO SE MONTA A HEAP ? 90 23 4 67 -8 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Filho direito= 2*2+1 Filho direito= 5 Filho esquerdo= 2*2+2 Filho esquerdo= 6 23 4 67 -8 90 S P 1 2 3 4 54 5 21 6

13. COMO SE MONTA A HEAP ? 90 23 4 67 -8 54 21 23 4 67 -8 90 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Nó pai=(i) Nó pai=(3) 1 2 3 4 5 6

14. COMO SE MONTA A HEAP ? 90 23 4 67 -8 54 21 Nó Pai= ( i ); Filho direito= 2 i +1; Filho esquerdo= 2 i +2; i 0 1 2 3 4 5 6 Filho direito= 2*3+1 Filho direito= 7 Filho esquerdo= 2*3+2 Filho esquerdo= 8 23 4 67 -8 90 S P 1 2 3 4 54 5 21 6 FILHOS SÃO MAIORES QUE O VETOR HEAP ORGANIZADA

15. 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. 222 2º for: Pega o maior elemento da hip e coloca na posição corresponde no array . Reconstrói a HIP

16. 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. 222 2º for: Pega o maior elemento da hip e coloca na posição corresponde no array . Reconstrói a HIP

17. 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. I S E N A S P i 0 1 2 3 4 5 6 i=(N-1)/2 i=(7-1)/2 i=3 i=( N-1)/2 N úmeros de elementos. Ponteiro do vetor.

18. 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. I S E N A S P i 0 1 2 3 4 5 6 i=(N-1)/2 i=(7-1)/2 i=3 i=( N-1)/2 N úmeros de elementos. Ponteiro do vetor.

19. 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. 222 2º for: Pega o maior elemento da hip e coloca na posição corresponde no array . Z Y X Z Y X Pego o elemento que esta no topo da HIP E coloco numa variável auxiliar Z aux X Coloco o valor de X no inicio e copio o valor de aux para o fim Z

20. 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. 222 2º for: Pega o maior elemento da hip e coloca na posição corresponde no array . Z Y X Z Y X Pego o elemento que esta no topo da HIP E coloco numa variável auxiliar Z aux X Coloco o valor de X no inicio e copio o valor de aux para o fim Z

21. 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. 222 2º for: Pega o maior elemento da hip e coloca na posição corresponde no array . Reconstrói a Heap Esta Função é responsável por chamar a função criaHeap , a qual vamos ver a seguir.

22. 2ª FUNÇÃO PARA ORDENAR VALORES 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 X X W X

23. 2ª FUNÇÃO PARA ORDENAR VALORES 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 X X W X

24. 2ª FUNÇÃO PARA ORDENAR VALORES 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 não, atribui um valor para J maior que o vetor. Antigo pai ocupa o lugar do ultimo filho analisado. X Y X X W X Z

25. HEAPSORT NÁ PRÁTICA

26. 23 4 67 -8 90 54 21 90 23 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=3 1 2 3 NA PRATICA! i=(7-1)/2 void heapsort ( int * vet , int N){ int i, aux ; for (i=(N-1)/2; i>=0; i--){ criaHeap ( vet , i, N-1); } i=( N-1)/ 2 NÃO TEM FILHOS 23 4 67 -8 90 54 21 i=2 1 2 3 23 4 67 -8 90 54 21 i=1 1 2 3 23 90 67 -8 4 54 21 i=0 1 2 3 -8 67 PAI 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

27. 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 restante i=N-1 4 90 23 67 -8 54 21 i 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 criaHeap ( vet , 0, i-1); 67 23 54 -8 4 21 90 21 90 67 21 4 67 23 54 -8 21 90 i 0 1 2 3 4 5 6 90 54 21 90

28. 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 restante i=N-1 i=5 67 aux criaHeap ( vet , 0, i-1); 4 67 23 54 -8 21 90 i 0 1 2 3 4 5 6 67 23 54 -8 4 21 90 21 23 54 -8 4 67 90 67 54 21 54 23 21 -8 4 67 90 4 54 23 21 -8 67 90 i 0 1 2 3 4 5 6 67 21 67

29. 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 restante i=N-1 i=4 54 aux criaHeap ( vet , 0, i-1); 54 23 21 -8 4 67 90 54 23 4 21 -8 67 90 i 0 1 2 3 4 5 6 4 23 21 -8 54 67 90 4 23 23 4 21 -8 54 67 90 4 54 23 21 -8 67 90 i 0 1 2 3 4 5 6 54 4 54 54

30. 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 restante i=N-1 i=3 23 aux criaHeap ( vet , 0, i-1); 54 21 4 -8 2 3 67 90 i 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 54 23 4 21 -8 67 90 i 0 1 2 3 4 5 6 -8 23 23 2 3

31. 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 restante i=N-1 i=2 21 aux criaHeap ( vet , 0, i-1); 54 21 4 -8 2 3 67 90 i 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 54 4 -8 21 2 3 67 90 i 0 1 2 3 4 5 6 -8 21 21

32. 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 restante i=N-1 i=1 4 aux criaHeap ( vet , 0, i-1); -8 4 21 23 54 67 90 4 -8 21 23 54 67 90 54 4 -8 21 2 3 67 90 i 0 1 2 3 4 5 6 54 -8 4 21 2 3 67 90 i 0 1 2 3 4 5 6 -8 4 21 23 54 67 90 FIM DO FOR -8 4 4

33. NA PRATICA! 54 -8 4 21 2 3 67 90 i 0 1 2 3 4 5 6 -8 4 21 23 54 67 90 ORDENADO -8

34. IMAGENS ILUSTRADAS GENÉRICO ESPECÍFICO

35. COMPARAÇÃO COM OUTROS ALGORITMOS Valores iguais Decrescente Semi organizadas Números aleatórios

36. 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.

37. CONSIDERAÇÕES FINAIS É 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

38. 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 . CONSIDERAÇÕES FINAIS

39. Obrigado! Duvidas ?