Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps - Coggle Diagram

- - - - Assim os elementos do array serão removidos em ordem decrescente
        
        Como na implementação em array de heap o elemento a ser removido é colocado por último, o array resultante será igual ao array original porém ordenado em ordem crescente
- - - - Deletar ítem com maior prioridade
      - Adicionar um novo ítem
      - Encontrar ítem com maior prioridade
    - - Utilizado também em
        
        Djikstra
        
        Codificação Huffman
        
        Algorítmo de Prim
        
        Heapsort
      - Noções de heap
        
        Árvore binária com uma chave atribuída a cada nó, com condições
        
        Prioridade da forma - todos os níveis da árvore binária estão cheios (ou quase), ex: todos níveis estão cheios exceto o último, no qual podem faltar algumas folhas à extrema direita.
        
        Dominância parental / propriedade "heap" - a chave em um nó é maior ou igual a chave dos seus filhos
        
        Os valores das chaves de uma heap estão ordenados de forma "top down", a sequência de valores em um caminho da raiz para alguma folha é não-crescente
        
        Não há relação entre os valores das chaves para nós no mesmo nível da árvore, ou nas subárvores da esquerda ou direita do mesmo nó
        
        Propriedades importantes das heaps
        
        A raiz da heap contém o maior elemento
        
        Os nós de uma heap (e os seus descendentes) também são uma heap
        
        Existe exatamente uma árvore binária essencialmente completa com n nós, e sua altura é igual a floor(log2 n)
        
        Uma heap pode ser implementada com um array, registrando seus elementos de cima pra baixo, da esquerda pra direita. É conveniente usar as posições de 1 a n, deixando H[0] inutilizado ou como valor sentinela (o maior valor da heap)
        
        Os nós pais estarão na primeira metade do array, e os nós filhos estarão na última metade
        
        Os filhos de um nó na posição i (1 <= i <= floor(n/2)) estarão nas posições 2i e 2i+1, o pai de um nó na pos i (2 <= i <= n) estará na posição floor(i/2)
        
        A implementação mais eficiente de heap geralmente é em array
        
        Principais formas de construção de heap
        
        Heap descendente
        
        1 more item...
        
        Heap ascendente
        
        2 more items...