PAA 06 Heapsort

Prévia do material em texto

Pesquisa e Ordenação: Pesquisa e Ordenação: 
HeapsortHeapsort
Rodrigo VerasRodrigo Veras
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 22
RoteiroRoteiro
 Introdução;
 Ordenação;
 Estrutura Heap;
 Principais Características;
 Tipos de Heap;
 Heapsort;
 Funcionamento do Método;
 Definição do Algoritmo;
 Comparação com outros algoritmos;
 Revisão;
 Exercícios;
IntroduçãoIntrodução
OrdenaçãoOrdenação
IntroduçãoIntrodução
 Pesquisa e Ordenação são operações
fundamentais em computação;
 Existem muitos algoritmos de pesquisa de
ordenação.
 A escolha do algoritmo depende das
propriedades dos dados.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 44
OrdenaçãoOrdenação
 Ordenação:
 É o ato de se colocar os elementos de uma sequência
de informações, em uma ordem predefinida.
 O termo técnico em inglês para ordenação é sorting,
cuja tradução literal é "classificação".
 Dado uma seqüencia de n dados: <a1,a2,...,an>
 O problema de ordenação é uma permutação
<a1’,a2’,...,an’> dessa seqüencia tal que:
 a1’ ≤ a2’ ≤ ... ≤an’ para alguma relação de ordem.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 55
OrdenaçãoOrdenação
 Um Algoritmo que ordena uma conjunto,
geralmente representada num vetor, é
chamadado um algoritmos de ordenação.
 Entre os mais importantes, podemos citar
 Bubble sort (ou ordenação por flutuação);
 Insertion sort (ou ordenação por inserção);
 Merge sort (ou ordenação por mistura);
 Heapsort (ou ordenação por heap);
 Quicksort.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 66
Estrutura Estrutura HeapHeap
Principais CaracterísticasPrincipais Características
Tipos de HeapTipos de Heap
HeapHeap
 A estrutura de dados Heap (binário) é um arranjo
que pode ser visto como uma árvore binária
praticamente completa.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 88
77 55 60 50 30 44 55 22
77
55 60
50 30 44 55
22
HeapHeap
 Cada nó da árvore corresponde a um elemento
do arranjo que armazena o valor no nó;
 A árvore está completamente preenchida em
todos os níveis, exceto possivelmente no nível
mais baixo, que é preenchido da esquerda para a
direita até certo ponto
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 99
Heap: DefiniçõesHeap: Definições
 Comprimento do arranjo:
 Número de elementos do arranjo;
 comprimento(A);
 Tamanho do heap:
 Número de elementos do heap armazenados no
arranjo;
 tamHeap(A);
 Para todo heap: tamHeap(A) ≤ comprimento(A);
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1010
Heap: DefiniçõesHeap: Definições
 O elemento A[1] é a raiz da árvore;
 Determinação das relações de um nó i;
 Determinação do pai:
 Pai(i) = Piso(i/2);
 Determinação do filho à esquerda:
 Esquerda(i) = 2*i;
 Determinação do filho à direita:
 Direita(i)= 2*i + 1;
 Exemplo:
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1111
77 55 60 50 30 44 55 22
Exemplo de uma HeapExemplo de uma Heap
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1212
77 55 60 50 30 44 55 22
77
55 60
50 30 44 55
22
Heap MáximoHeap Máximo
 A[pai(i)] ≥ A[i].
 Isto é, o valor de um nó é no máximo o valor de seu
pai.
 O maior elemento do heap está na raiz.
 As subárvores de um nó possuem valores
menores ou iguais ao do nó.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1313
Heap MínimoHeap Mínimo
 A[pai(i)] ≤ A[i].
 Isto é, o valor de um nó é maior ou igual o valor de seu
pai.
 O menor elemento do heap está na raiz;
 As subárvores de um nó possuem valores
maiores ou iguais ao do nó.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1414
HeapsortHeapsort
Funcionamento do MétodoFuncionamento do Método
Definição do AlgoritmoDefinição do Algoritmo
ComparaçãoComparação
Funcionamento do MétodoFuncionamento do Método
 Suponhamos que um arranjo A implementado
sobre um vetor de N elementos.
 O algoritmo de Heapsort para ordenação deste
arranjo consiste em duas fases:
 Construção do Heap H a partir do arranjo A dado;
 Retirada repetida da raiz de H.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1616
Construção do HeapConstrução do Heap
 A construção da estrutura heap pode ser
realizada em dois passos:
 Coloca-se o Item a ser inserido no final da árvore;
 Move-se esse Item na árvore até que fique num local
apropriado;
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1717
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1818
44, 30, 50, 22, 60, 55, 77, 55
44
44
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 1919
44 30
44, 30, 50, 22, 60, 55, 77, 55
44
30
 Vetor Atualizado
Construção do Heap: ExemploConstrução do Heap: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2020
44, 30, 50, 22, 60, 55, 77, 55
44 30 50
44
30 50
 Vetor Atualizado
Construção do Heap: ExemploConstrução do Heap: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2121
44, 30, 50, 22, 60, 55, 77, 55
50 30 44
50
30 44
 Vetor Atualizado
Construção do Heap: ExemploConstrução do Heap: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2222
44, 30, 50, 22, 60, 55, 77, 55
50 30 44 22
50
30 44
22
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2323
44, 30, 50, 22, 60, 55, 77, 55
50 30 44 22 60
50
30 44
22 60
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2424
44, 30, 50, 22, 60, 55, 77, 55
50 60 44 22 30
50
60 44
22 30
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2525
44, 30, 50, 22, 60, 55, 77, 55
60 50 44 22 30
60
50 44
22 30
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2626
44, 30, 50, 22, 60, 55, 77, 55
60 50 44 22 30 55
60
50 44
22 30 55
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2727
44, 30, 50, 22, 60, 55, 77, 55
60 50 55 22 30 44
60
50 55
22 30 44
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2828
44, 30, 50, 22, 60, 55, 77, 55
60
50 55
22 30 44 77
60 50 55 22 30 44 77
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 2929
44, 30, 50, 22, 60, 55, 77, 55
60
50 77
22 30 44 55
60 50 77 22 30 44 55
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 3030
44, 30, 50, 22, 60, 55, 77, 55
77 50 60 22 30 44 55
77
50 60
22 30 44 55
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 3131
44, 30, 50, 22, 60, 55, 77, 55
77
50 60
22 30 44 55
55
77 50 60 22 30 44 55 55
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisae Ordenação: HeapsortPesquisa e Ordenação: Heapsort 3232
44, 30, 50, 22, 60, 55, 77, 55
77
50 60
55 30 44 55
22
77 50 60 55 30 44 55 22
Construção do Heap: ExemploConstrução do Heap: Exemplo
 Vetor Atualizado
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 3333
44, 30, 50, 22, 60, 55, 77, 55
77 55 60 50 30 44 55 22
77
55 60
50 30 44 55
22
Construção do HeapConstrução do Heap
 Observações:
 Os nós folhas constituem um heap máximo de 1
elemento;
 Na representação em forma de vetores, os nós folhas são
indexados pelos índices de (n/2 +1) a n.
 Ao inserirmos um novo elemento a propriedade do
heap pode ser quebrada;
 Deve-se percorrer os nós da árvore para verificação da
propriedade;
 Caso necessário, reajustar a posição dos nós;
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 3434
Algoritmo de ConstruçãoAlgoritmo de Construção
Algoritmo constroiHeapMax(A)
tamHeap(A) = comprimento(A);
para i = Piso(comprimento(A)/2) até 1 faça
refazHeapMax(A,i);
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 3535
Manutenção da PropriedadeManutenção da Propriedade
Algoritmo refazHeapMax(A,i)
e = esquerda(i);
d = direita(i);
se (e≤ tamHeap(A) E A[e] > A[i]) então
maior = e;
senão
maior = i;
se (d≤ tamHeap(A) E A[d] > A[maior]) então
maior = d;
se (maior ≠ i) então
trocar (A[i], A[maior])
refazHeapMax(A,maior);
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 3636
Ordenação do ArranjoOrdenação do Arranjo
 Ordenação em Ordem crescente:
 O primeiro elemento do arranjo é o maior elemento
do heap;
 Troca-se o primeiro elemento pelo ultimo e diminui-se
o tamanho do heap:
 O maior elemento já está na posição;
 O heap pode ter deixado de ser um heap máximo;
 Deve-se reconstruir o heap.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 37
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 38
77
55 60
50 30 44 55
22
77 55 60 50 30 44 55 22
tamHeap(A)= 8;
Troca(A[1], A[8]);
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 39
22 55 60 50 30 44 55 77
tamHeap(A)= 8;
22
55 60
50 30 44 55
77
tamHeap(A) --;
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 40
22 55 60 50 30 44 55 77
tamHeap(A)= 7;
22
55 60
50 30 44 55
77
refazHeapMax(A,1));
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 41
60 55 55 50 30 44 22 77
tamHeap(A)= 7;
60
55 55
50 30 44 22
77
Troca(A[1], A[7]);
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 42
22 55 55 50 30 44 60 77
tamHeap(A)= 7;
22
55 55
50 30 44 60
77
tamHeap(A) --;
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 43
22 55 55 50 30 44 60 77
tamHeap(A)= 6;
22
55 55
50 30 44 60
77
refazHeapMax(A,1));
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 44
55 50 55 22 30 44 60 77
tamHeap(A)= 6;
55
50 55
22 30 44 60
77
Troca(A[1], A[6]);
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 45
44 50 55 22 30 55 60 77
tamHeap(A)= 6;
44
50 55
22 30 55 60
77
tamHeap(A) --;
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 46
44 50 55 22 30 55 60 77
tamHeap(A)= 5;
44
50 55
22 30 55 60
77
refazHeapMax(A,1));
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 47
55 50 44 22 30 55 60 77
tamHeap(A)= 5;
55
50 44
22 30 55 60
77
Troca(A[1], A[5]);
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 48
30 50 44 22 55 55 60 77
tamHeap(A)= 5;
30
50 44
22 55 55 60
77
tamHeap(A) --;
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 49
30 50 44 22 55 55 60 77
tamHeap(A)= 4;
30
50 44
22 55 55 60
77
refazHeapMax(A,1));
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 50
50 30 44 22 55 55 60 77
tamHeap(A)= 4;
50
30 44
22 55 55 60
77
Troca(A[1], A[4]);
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 51
22 30 44 50 55 55 60 77
tamHeap(A)= 4;
22
30 44
50 55 55 60
77
tamHeap(A) --;
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 52
tamHeap(A)= 3;
22
30 44
50 55 55 60
77
22 30 44 50 55 55 60 77
refazHeapMax(A,1));
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 53
tamHeap(A)= 3;
44
30 22
50 55 55 60
77
44 30 22 50 55 55 60 77
Troca(A[1], A[3]);
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 54
tamHeap(A)= 3;
22
30 44
50 55 55 60
77
22 30 44 50 55 55 60 77
tamHeap(A) --;
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 55
tamHeap(A)= 2;
22
30 44
50 55 55 60
77
22 30 44 50 55 55 60 77
refazHeapMax(A,1));
2.1 2.1 -- Funcionamento Do Método( 2ª Fase )Funcionamento Do Método( 2ª Fase )
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 56
tamHeap(A)= 2;
30
22 44
50 55 55 60
77
30 22 44 50 55 55 60 77
Troca(A[1], A[2]);
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 57
tamHeap(A)= 2;
22
30 44
50 55 55 60
77
22 30 44 50 55 55 60 77
tamHeap(A) --;
Ordenação do Arranjo: ExemploOrdenação do Arranjo: Exemplo
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 58
tamHeap(A)= 1;
22
30 44
50 55 55 60
77
22 30 44 50 55 55 60 77
Fim do Algoritmo
Vetor Ordenado
Algoritmo HeapsortAlgoritmo Heapsort
Algoritmo Heapsort(A)
constroiHeapMax(A)
Para i= comprimento(A) até 2 faça
Trocar(A[1], A[i]);
tamHeap(A)--;
refazHeapMax(A,1);
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 5959
ComparativoComparativo
Algoritmo Pior Caso Caso Médio
Insertion Sort O(n2) O(n2)
Selection Sort O(n2) O(n2)
Bubble Sort O(n2) O(n2)
Merge-Sort O(n log2n ) O(n log2n )
Heapsort O(n log2n ) O(n log2n )
Quicksort O(n2) O(n log2n )
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 6060
RevisãoRevisão
 A solução dos problemas de pesquisa e
ordenação são de suma importância para a
computação;
 O heapsort é um poderoso algoritmo para
ordenação de dados;
 Ele utiliza uma estrutura heap para armazenar os
dados;
 Um heap binário é uma árvore binária
paraticamente completa;
 Um heap pode ser máximo ou mínimo;
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 6161
RevisãoRevisão
 O algoritmo heapsort possui duas fases:
 Construção do heap;
 Remoção da raiz do heap; Ao final, obtém-se um arranjo ordenado;
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 6262
ExercíciosExercícios
 Onde, em um heap máximo, o menor elemento
poderia residir, supondo-se que todos os
elementos sejam distintos?
 A seqüência <23, 17, 14, 6, 13, 10, 1, 5, 7, 12> é
um heap máximo?
 Um arranjo que está em sequência ordenada é
um heap mínimo?
 Quais são os números mínimo e máximo de
elementos em um heap de altura h?
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 6363
ExercíciosExercícios
 Mostre que um heap de n elementos tem altura
Piso(log2n).
 Qual é o efeito de chamar refazHeapMax(A,i)
quando A[i] é maior que seus filhos?
 Qual é o efeito de chamar refazHeapMax(A,i)
quando i > compHeap/2?
 Siga a operação do algoritmo HeapSort sobre o
arranjo A = <5,13,2, 25, 7, 17, 20, 8, 4>.
Pesquisa e Ordenação: HeapsortPesquisa e Ordenação: Heapsort 6464