Please enable JavaScript.

Coggle requires JavaScript to display documents.

IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram

- - - - Multiconjunto de itens
        
        Prioridade do item
        
        Característica ordenável
      - Operações
        
        Achar um item com a maior prioridade
        
        Deletar um item com a maior prioridade
        
        Adicionar um novo item ao multiconjunto
    - - Prim
      - Dijkstra
      - Ordenação (Heapsort)
    - - Árvore binária com chaves em seus nós
      - Uma chave por nó
      - Condições
        
        Propriedade do formato (shape property)
        
        Árvore estar completa a menos das folhas mais a direita
        
        Dominância parental (parental dominance)
        
        Chave de cada nó maior ou igual as chaves dos seus filhos
        
        Automaticamente satisfeita
        
        max-heap
        
        min-heap
      - Valores da chave ordenados de cima para baixo
      - Valores da chave não tem ordem da esquerda para a direita
      - Propriedades
        
        Exatamente uma árvore binária completa com n nós
        
        Altura: floor(log n na base 2)
        
        A raiz de um heap sempre contém seu maior elemento
        
        Um nó de um heap com seus descendentes também é um heap
        
        Pode ser implementado com array
        
        H[0] não é usado
        
        Nós internos: primeiras floor(n/2) posições
        
        Folhas: Últimas ceil(n/2) posições
        
        Propriedade para filho
        
        Propriedade para pai
      - Alternativas de construção
        
        Bottom-up
        
        Elementos previamente conhecidos
        
        Todos os elementos inseridos de uma vez
        
        "Heapifica" do último para o primeiro nó interno
        
        Eficiência para o pior caso na criação do Heap: O(n)
        
        Top-Down
        
        Elementos não conhecidos previamente
        
        Elementos inseridos um por um
        
        "Heapifica" a cada inserção
        
        Eficiência na inserção é O(log n)
        
        Deleção da chave máxima
        
        Eficiência é O(log n)
        
        Menos eficiente na criação
    - - Algoritmo de ordenação
      - Fases
        
        Construção do heap a partir do Array
        
        Deleções máximas (Maximum deletions): Aplica a deleção da raiz n-1 vezes ao heap restante
      - Elementos do Array eliminados em ordem decrescente
        
        Array resultante é a original ordenada de forma crescente
      - Eficiência
        
        Caso médio e pior: θ(n log n)
        
        Mesma classe do mergesort
        
        Não requer espaço extra no armazenamento
        
        Mais lento que o quicksort