Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps and Heapsort, Heaps, Heapsort - Coggle Diagram
-
Heaps
Eficiência:
Método bottom-up:
- No pior caso do método bottom-up: C(n) = 2(n - log(n-1)), onde n é a quantidade de nós.
Ou seja, no pior caso uma heap de tamanho n pode ser construída com um pouco menos que 2n comparações
Método top-down:
- A operação de inserir não pode fazer mais comparações do que o tamanho da árvore, e como o tamanho da árvore h é igual log n, então a operação de inserção ∈ O(n)
A quantidade de comparações feitas pela heapify da remoção não pode ser maior que a altura da árvore, portanto a eficiência da remoção é O(log n)
-
É uma estrutura de dados parcialmente ordenada que é especialmente adequada para implementar filas de prioridade ( que seria um conjunto de elementos com uma característica solicitável, chamada de prioridade de um item) com as operações de remover o item com mais prioridade, encontrar um item com a maior prioridade, e adicionar um novo elemento na fila
Uma heap pode ser definida como uma árvore binária, onde cada nó é uma key, que segue as seguintes restrições:
- the shape property (que seria quando a árvore está essencialmente cheia, ou totalmente cheia(menos o último nível onde apenas algumas folhas mais à direita podem estar vazias)
- the parental dominance or heap property (que seria a key de um nó é sempre maior ou igual que as keys dos nós dos seus filhos)
*Note que não há relação entre os valores das keys do mesmo level
Características das heaps:
- Existe exatamente uma árvore binária de tamanho n completamente cheia
- A raiz sempre contém o maior elemento
- Um nó de uma heap junto com todos os seus descendentes também são considerados uma heap
- Uma heap pode ser representada como um array, escrita da forma top-down, left-right, por exemplo na pg 228 do Levitin. É interessante deixar a primeira posição do array (arr[0]) vazia
*Embora normalmente é mais fácil de entender a heap como uma árvore binária, é mais fácil e mais eficiente implementa-la como array
Remoção da raiz:
- 1) trocasse a raiz de lugar com a última key da heap
- 2) decrescer o tamanho da heap em 1
- 3) Heapify o nó que ficou na raiz, assim como no método bottom-up, trocando de posição entre ele e o maior dos seus filhos até que esse nó tenha a restrição de dominância parental
Heapsort
É um algoritmo de inserção de 2 estágios:
- 1) heap construction (construir uma heap a partir de um dado array)
- 2) maximum deletions (aplicar o algoritmo de remoção da raiz n-1 vezes para a heap restante)
Como resultado, os elementos do array são eliminados em ordem decrescente. Mas, uma vez que na implementação de array de heaps, um elemento que está sendo excluído é colocado por último, o array resultante vai ser o array original ordenado em ordem crescente (ver imagem da pg 232 do Levitin)
Eficiência: Como sabemos que construir a heap é O(n), e podemos checar na pg 232 do Levitin que a parte de maximum deletions é O(n log n), a eficiêcia do Heapsort é O(n) + O(n log n) = O(n log n). Uma análise mais aprofundada do heapsort mostra que a eficiência dele é de fato Θ(n log n) tanto no pior caso quanto no caso médio. Portanto a eficiência temporal do heapsort cai na mesma classe que a do mergesort, embora ele não gaste tanta memória quanto o mergesort, mas ele ainda é um pouco mais lento que o quicksort