Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 10 - Coggle Diagram

- - - - Achar o elemento com a maior prioridade
      - Deletar o elemento de maior prioridade
      - Introduzi um novo elemento
  - - - Recomenda-se que os nós da heap comecem do índice 1 e termine no índice n; enquanto no índice 0, ou fica vazio, ou é colocado um valor maior que o da raiz
      - Os nós parentais vão ocupar os primeiros ⌊n/2⌋ índices, enquanto as folhas vão ocupar os últimos ⌈n/2⌉ índices
      - Os filhos de uma chave com índice i na array vão ter índices iguais a 2i e 2i+1.
        Enquanto o índice do pai de uma chave com índice i será ⌊i/2⌋
        
        Com isso pode-se dizer que uma heap H[1,...,n] implementada por uma array, que os itens com índice i da primeira metade da array, sempre serão maiores, ou iguais, aos itens de índices 2i e 2i+1
      - Implementação por árvores binárias favorece o entendimento dos algoritmos para heaps;
        
        Implementação por array facilita a implementação desses algoritmos;
  - - - Top-down
        
        Elementos não-conhecidos são inseridos um por um
        
        Basicamente, você adiciona uma nova chave como uma folha da heap, depois disso você "heapifica" a árvore, para que o a chave inserida fique na posição certa da árvore. Isso se repete até que todas as chaves tenham sido inseridas
        
        heapify é uma operação que visa manter a parental dominance em uma heap que teve um elemento novo inserido, trocando as chaves entre um pai e um filho(a chave nova), até que essa condição seja atingida
        
        Eficiência de pior-caso de inserção: O(log(n))
        
        Eficiência de pior-caso de criação: O(n log(n))
        
        Usado tanto para inserção de elemento, como criação de uma heap
      - Bottom-up
        
        Basicamente, vai do último (H[n]) até o elemento H[x] da array, fazendo os seguintes passos:
        
        1) Vê se o pai tem dois filhos, ou não
        
        1.5) Se tiver, verifica e escolhe qual criança tem a maior chave para continuar com o processo
        
        2) Verifica se o pai é menor que o nó atual
        
        3) Se ele for menor, então troca a posição das duas chaves; caso contrário, deixa como está
        
        4) Segue para o índice anterior
        
        Tal que x será o primeiro índice a ter o resultado 1 = ⌊x/2⌋, pois esse será o primeiro filho da raiz da heap
        
        Eficiência de pior-caso: O(n) = 2(n - log₂(n-1))
        
        Todos os elementos já devem estar inseridos na array
    - - Para isso, você precisa fazer os seguintes passos:
        
        1) Trocar a chave da raiz com a do último elemento (pensa na array)
        
        2) Diminui o tamanho da heap em 1 (pensa em array)
        
        3) "Heapifica" a árvore até a parental dominance for alcançada
      - Eficiência de pior-caso: O(log(n))
- - - - Isso lhe torna pior que Quicksort, mas semelhante ao Mergesort