Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps e algoritmo Heapsort - Coggle Diagram
Heaps e algoritmo Heapsort
Uma
heap
é uma estrutura de dados parcialmente ordenada
Especialmente usada para implementar
filas de prioridades
Uma
filas de prioridade
é uma coleção de itens com uma característica ordenável, que é chamada de
prioridade
do item
Uma
heap
é uma árvore binária com uma chave associada a cada um de seus nós
Duas condições precisam ser satisfeitas
Propriedade formal
A árvore binária está
quase completa
Todos os seus níveis necessitam estarem cheios, exceto o último, no qual pode estar faltando apenas a folha mais à direita
Dominação parental ou propriedade de heap
A chave de cada nó é maior ou igual às chaves de seus nós filhos
Seguindo estas condições, os valores das chaves são ordenados de cima para baixo
Os valores da raíz para as folhas são não-crescentes
Propriedades das heaps
Existe exatamente uma árvore binária completa com \(n\) nós
Sua altura é \(\lfloor \log_{2} n\rfloor\)
A raíz de uma heap sempre contém seu maior elemento
Um nó de uma heap em conjunto com todos os seus descendentes também é uma heap
Uma heap pode ser implementada como um array ao armazenar seus elementos de cima para baixo e da esquerda para a direita
Armazenar os elementos da heap nas posições de 1 até \(n\), com a posição 0 sem ser usada ou contendo um elemento para demarcar o local
As chaves dos nós parentais estarão nas primeiras \(\lfloor n/2\rfloor\), enquanto que as chaves das folhas estarão nas \(\lceil n/2 \rceil\) posições finais
2 maneiras principais de construir uma heap
De baixo para cima
Inicializa a árvore binária com \(n\) nós colocando as chaves na ordem dada e depois transforma a árvore em heap
Para transformar a árvore em heap, o algoritmo checa a propriedade de dominância parental do último nó pai
Se a
propriedade não for atendida
, então a
chave do nó pai
é
menor
que a
chave do nó filho
, de forma que o algoritmo às troca
Após isso, o algoritmo repete esse processo para o nó pai anterior e
para depois que esse processo é feito para a raíz da árvore
Eficiência temporal
\(O(n)\)
De cima para baixo
Conectar um novo nó com chave K na última folha da heap
Mover K para seu lugar apropriado
Comparar K com a chave em seu nó pai
Se a chave em seu nó pai for maior ou igual, não é necessário mudá-los de lugar
As trocas continuam até que K não seja maior que seu nó pai ou até que K seja a raíz da árvore
A
eficiência temporal
pertence a \(O(\log n)\)
Se K for maior, o algoritmo os troca de lugar e compara K com a chave de seu novo nó pai
Deletar a chave da raíz
Trocar a chave da raíz com a chave K da última folha de uma heap
Diminuir o tamanho da heap em 1, excluindo a folha com a chave que era a raíz
Transformar a árvore menor em heap movendo K da mesma maneira que na construção de uma heap de
baixo para cima
A
eficiência temporal
pertence a \(O(\log n) \)
Algoritmo
heapsort
Possui 2 fases
Construir uma heap
dado um array
Aplicar a remoção da raíz
\(n-1\) vezes na heap que restou
Os elementos do array são removidos em ordem decrescente
Gera um array em ordem crescente, já que o elemento removido é colocado no último lugar
Eficiência temporal
\(O(n\log n)\)
Não requer espaço extra