Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps and Heapsort - Coggle Diagram

- - - - encontrar um item com a prioridade mais alta (ou seja, a maior)
        excluir um item com a prioridade mais alta
        adicionando um novo item ao multiset
    - - agendamento de execuções de tarefas por sistemas operacionais de computador
        
        gerenciamento de tráfego por redes de comunicação
        surgem em vários algoritmos importantes, por exemplo:
        
        algoritmo de Prim;
        
        algoritmo de Dijkstra;
        
        codificação de Huffman;
        
        aplicações branch-and-bound.
        serve como pedra angular de um algoritmo de classificação teoricamente importante chamado heapsort.
  - - - A dominância parental ou propriedade de heap — a chave em cada nó é maior ou igual às chaves em seus filhos. (Esta condição é considerada automaticamente satisfeita para todas as folhas.)
        
        eficiência da exclusão
        
        A eficiência da exclusão é determinada pelo número de comparações de chave necessárias para “heapificar” a árvore após a troca ter sido feita e o tamanho da árvore ser reduzido em 1
        
        eficiência de tempo de deleção está em O(log n)
      - A propriedade de forma – a árvore binária é essencialmente completa (ou simplesmente completa), ou seja, todos os seus níveis estão cheios, exceto possivelmente o último nível, onde apenas algumas folhas mais à direita podem estar faltando.
    - - No entanto, não há ordem da esquerda para a direita nos valores de chave
- - - - Estágio 2 (exclusões máximas): Aplicar a operação de exclusão de raiz n−1 vezes
        para a pilha restante
    - - Eficiência
        
        a eficiência de tempo do heapsort se enquadra na mesma classe que a do mergesort
        
        Experimentos de tempo em arquivos aleatórios mostram que o heapsort é executado mais lentamente do que o quicksort, mas pode ser competitivo com o mergesort.