4 Heapsort

Prévia do material em texto

3. Ordenação por Seleção 
 
3.1. Heapsort 
 
 Como vamos ver mais adiante, o heapsort tem um tempo de execução de . 
A grande vantagem é que a ordenação é feita localmente, ou seja, apenas um número 
constante de elementos do arranjo é armazenado fora do arranjo de entrada em qualquer 
instante, como acontece nos algoritmos de inserção. 
 O heapsort introduz outra técnica de projetos de algoritmos que é o uso de estruturas 
de dados, neste caso uma estrutura que chamamos de “heap” (ou “monte”), para gerenciar 
informações durante a execução do algoritmo. 
3.2. Heaps 
A estrutura de dados heap (binário) é uma estrutura que pode ser vista como uma árvore 
binária praticamente completa, conforme Figura 1. Cada nó da árvore corresponde a um 
elemento do arranjo que armazena o valor do nó. A árvore está completamente preenchida 
em todos os níveis, exceto no nível mais baixo, que é preenchido da esquerda até certo ponto. 
 
 
(a) (b) 
Figura 3.1- Um heap máximo visto como (a) uma árvore binária e (b) como um arranjo. 
 
Um arranjo A que representa um heap é um objeto com dois atributos: [ ], que 
é o número de elementos do arranjo, e [ ], o número de elementos no 
heap armazenado dentro do arranjo A. Ou seja, embora [ [ ]] possa conter 
números válidos, nenhum elemento além de [ [ ]], onde tamanho-do-
heap[A] ≤ comprimento[A], é um elemento do heap. A raiz da árvore é A[1] e, dado o índice 
de um nó, os índices de seu pai , do filho da esquerda e do filho da 
diretira podem ser calculados de modo simples: 
 
 
 return ⌊ ⁄ ⌋ 
 
 
 return 
 
 
 return 
 
Observação: 
 
 
⌊ ⁄ ⌋ 
 
 Existem dois tipos de heaps binários, os heaps máximos e os heaps mínimos. Em um 
heap máximo, para todo nó diferente da raiz, 
 
 [ ] [ ], 
 
isto é, o valor de um nó é no máximo o valor de seu pai. Desse modo, o maior elemento em 
um heap máximo é armazenado na raiz, e a subárvore que tem raiz em um nó contém valores 
menores que o próprio nó. Já o heap mínimo organizado de modo oposto onde para todo nó 
diferente da raiz, 
 
 [ ] [ ]. 
 
O menor elemento do heap mínimo está na raiz. 
 
 Visualizando um heap como uma árvore, definimos a altura de um nó como o número 
de arestas no caminho descendente simples mais longo desde o nó até uma folha, e definimos 
a altura do heap como a altura de sua raiz. Tendo em vista que um heap de elementos é 
baseado em uma árvore binária completa, sua altura é . Veremos que as operações 
básicas sobre as heaps são executadas em um tempo máximo proporcional à altura da árvore, 
e assim demora um tempo . 
 
3.3. Algoritmo MAX-HEAPIFY 
 
 Este algoritmo é utilizado para garantir que, caso [ ] seja menor que os filhos 
 e , violando assim a propriedade do heap máximo, o mesmo seja deslocado 
para baixo, de tal forma que o nó de índice se torne um heap máximo. 
 
 
1 
2 
3 if [ ] e [ ] [ ] 
4 then 
5 else 
6 if [ ] e [ ] [ ] 
7 then 
8 if 
9 then trocar [ ] [ ] 
10 
 
 
(a) 
 
(b) 
 
(c) 
 
Figura 3.2- A ação da chamada, , onde . (a) Configuração inicial 
com [ ] no nó violando a propriedade do heap máximo. A propriedade é restaurada para o nó em (b) ao 
trocar [ ] com [ ], oque destrói a propriedade para o nó . Em (c) propriedade é restaurada ao trocar [ ] com 
 [ ], finalizando com a chamada que não surte mais efeito. 
 
 O tempo de execução do algoritmo , em uma subárvore de tamanho 
com raiz em um determinado nó , é de , para arrumar a relação entre os elementos [ ], 
 [ [ ]] e [ [ ]], mais o tempo para rodar em uma subárvore com 
raiz em um dos filhos do nó (assumindo que ocorra uma chamada recursiva). As subárvores 
de cada filho tem um tamanho máximo de ⁄ - o pior caso ocorre quando o nível mais baixo 
está exatamente metade completo – e portanto o tempo de execução fica 
 
 ⁄ . 
 
Solucionando esta recorrência utilizando o caso 2 do teorema master: 
 
Para ⁄ 
 
Se ( ), então ( ) . 
 
Logo, o tempo de execução fica . 
 
3.4. Construindo um Heap 
 
 Podemos utilizar o algoritmo para converter um vetor [ ], onde 
 , em uma heap máximo. Se olharmos com atenção, veremos que os 
elementos do vetor [ ⌊ ⁄ ⌋ ] são todos folhas da árvore, ou seja, é um heap de 1 
elemento. Desta forma, o algoritmo percorre os demais elementos do 
vetor e roda o para cada um. 
 
 
1 
2 for ⌊ ⁄ ⌋ downto 1 
3 do 
 
 Uma simples análise do tempo de execução do algoritmo mostra 
que são realizadas chamadas de que tem um custo . Logo, o 
tempo de execução fica . Esta é uma aproximação que, apesar de correta, não 
representa o custo precisamente. 
 Podemos derivar uma análise mais precisa observando que o tempo de execução de 
 sobre um nó varia com a altura do nó na árvore, a maioria das alturas na 
árvore são pequenas. Esta análise mais restrita baseia-se nas propriedades de que um heap de 
 elementos tem altura ⌊ ⌋ e no máximo ⌈ ⁄ ⌉ nós de qualquer altura . 
 O tempo exigido por , quando chamado em um nó de altura é . 
Portanto 
 
∑ ⌈
 
 
⌉ ( ∑
 
 
⌊ ⌋
 
)
⌊ ⌋
 
 
 
Sabendo-se que, 
 
∑ 
 
 
 
 
 
 
E substituindo ⁄ , tem-se 
 
∑
 
 
 
 ⁄
 ⁄ 
 
 
 
 
 Deste modo, o tempo de execução para pode ser limitado como 
 . 
 
 
 
 
 
(a) (b) 
 
 
(c) (d) 
 
 
(e) (f) 
Figura 3.3 - A operação da chamada, 
 
 
3.5. O Algoritmo Heapsort 
 
 O algoritmo do heapsort começa com a construção de um heap máximo para o vetor 
 [ ], onde , através da chamada . Como o maior 
elemento do vetor está armazenado em [ ], podemos colocá-lo na posição correta apenas 
trocando-o com [ ] . Se agora descartarmos o nó da heap, podemos observar que os filhos 
da raiz são heaps máximos, porém a própria raiz pode estar violando o princípio do heap 
máximo. Tudo que precisamos fazer é restaurar a propriedade chamando 
 que irá criar um heap máximo para [ ]. O algoritmo heapsort 
então repete este processo para o heap máximo de tamanho até 2. 
 
 
 
1 
2 for downto 2 
3 trocar [ ] [ ] 
4 
5 
 
 O algoritmo heapsort tem um tempo de execução de já que a chamadaleva e cada chamadas de levam . 
 
 
(a) (b) 
 
(c) (d) 
 
(e) (f) 
 
(g) (h) 
 
 
(i) (j) 
 
 
 
(k) 
 
Figura 3.4 - A operação do algoritmo 
 
Exercícios para casa: 
 
1. Usando o vetor { }, mostre a operação dos algoritmos 
de ordenação: , , HEAPSORT e . 
 
2. Usando a Figura 4 como modelo, ilustre a operação do algoritmo 
para o vetor { }. 
 
3. Escreva o código para o algoritmo MERGESORT e mostre a operação do mesmo para o 
vetor { }. 
 
4. Escreva o código para o algoritmo INSERTSORT e mostre a operação do mesmo para o 
vetor { }. 
 
Exercícios desafio: 
 
5. O código para é muito eficiente exceto devido à chamada recursiva na 
linha 10, o que pode causar problemas dependendo da arquitetura onde rodará o mesmo. 
Escreva um código eficiente para que utilize um laço de repetição 
controlado ao invés de recursão. 
 
6. Porque o algorítimo inicia o loop do índice a partir 
⌊ ⁄ ⌋ e decresce até 1, ao invés de iniciar em 1 e crescer até 
⌊ ⁄ ⌋