Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap e Heapsort - Coggle Diagram
Heap e Heapsort
Heap
É uma estrutura de dados parcialmente ordenada utilizada para implementar uma priority queue (fila de prioridade)
Uma priority queue pode ser definida por um multiset de itens ordenavéis por uma característica - prioridade
Uma estrutura de heap pode ser ilustrada e definida como uma árvore binária, seguindo as seguintes condições:
Shape Property
A árvore deve ser parcialmente completa, apenas as folhas direitas do último nível da árvore podem ser vazias
Parental Dominance
Cada nó da heap deve obedecer o seguinte critério: a chave de um nó deve ser >= ou <= (maxheap, minheap) do que as chaves dos seus filhos
-
Bottom up construction
Todos os elementos são conhecidos antes da criação da heap, cada elemento é inserido de forma sequencial
Para garantir que a heap esteja cumprindo as condições são realizadas comparações para trocar as chaves de cada nó se necessário
Topdown construction
Os elementos não são conhecidos e são inseridos um por um, e o processo de heapify (comparações sucessivas para garantir o cumprimento das condições) ocorre a cada inserção
-