Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap e heapsort - Coggle Diagram
Heap e heapsort
Propriedades de Heaps:
- Existe exatamente uma árvore binária essencialmente completa com n nós de altura igual ao piso de log de n na base binária.
- A raíz da árvor sempre contém seu maior elemento.
- Um nó de uma heap, junto com todos o seus descendentes, também é uma heap.
- Uma Heap pode ser implementada como um array onde seus elementos são registrados a partir de uma abordagem top-down (left-to-right)
Quando bem implementada, uma Heap deve possuir pelo menos as seguintes operações
-
-
-
Uma heap pode ser definida como uma árvore binária cujos nós são assinados com suas chaves (keys), seguindo duas condições:
Propriedade da forma (shape property): segundo essa condição, a árvore deve estar essencialmente completa (ou simplesmente completa), ou seja, todos os níveis da árvore binária devem possuir ambos os nós registrados (left e right), com exceção do último nível, o qual pode não dispor de seu nó mais à direita preenchido.
Dominância parental (parental dominance ou heap property): neste caso, para todos os nós, deve ser verdade que o valor de sua key é maior ou igual ao as keys registradas em seus nós descendentes.
-
Heapsort é um algoritmo de ordenação cujo resultado temos um array ordenado de forma crescente, mas cuja inserção foi feita do fim para o começo (right to left), ou seja, a heap foi desconstruída de forma decrescente.
Step-by-step
- construa uma heap para um array dado de tamanho n
- Aplique o algoritmo de deleção do nó root n - 1 vezes
Heaps são estruturas de dados parcialmente ordenadas bastante adequadas para a implementação de filas que apresentem níveis de prioridade (como a fila de atendimento hospitalar, por exemplo).
Heap é a estrutura de dados básica necessária para a implementação do algoritmo de ordenação chamado Heapsort.
OBS: a maioria dos algoritmos de heaps são definidos por meio de árvores binária, porém sua implementação por meio de arrays normalmente é mais simples e também mais eficiente.