Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps and Heapsort, Heapsort, Eficiência de inserção - Coggle Diagram

- - - - Operações
        
        encontrar um item com a prioridade mais alta (ou seja, maior)
        
        excluir um item com a prioridade mais alta
        
        adicionar um novo item ao multiset
  - - - a árvore binária está essencialmente 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.
    - - a chave em cada nó é maior ou igual às chaves de seus filhos.
  - - - uma árvore binária essencialmente completa com n nós. Sua altura é igual a [log2 n]
    - - A raiz de um heap sempre contém seu maior elemento.
    - - Um nó de um heap considerado com todos os seus descendentes também é um heap.
    - - Um heap pode ser implementado como um array registrando seus elementos de cima para baixo, da esquerda para a direita.
        
        b.
        
        os filhos de uma chave na posição parental do array i (1 ≤ i ≤ n/2 ) estarão nas posições 2i e 2i + 1 e, correspondentemente, o pai de uma chave na posição i (2 ≤ i ≤ n ) estará na posição i/2
        
        a.
        
        as chaves do nó parental estarão nas primeiras [n/2] posições do array, enquanto as chaves folha ocuparão as últimas [n/2] posições
  - - - inicializa a árvore binária essencialmente completa com n nós, colocando as chaves na ordem dada e então “amontoa” a árvore como segue.
        
        Começando com o último nó parental, o algoritmo verifica se a dominância parental é válida para a chave neste nó.
        
        Se não for válida, o algoritmo troca a chave K do nó pela chave maior de seus filhos e verifica se a dominância parental é válida para K em sua nova posição.
        
        Este processo continua até que a dominância parental para K seja satisfeita.
        
        o algoritmo prossegue fazendo o mesmo para o predecessor imediato do nó. O algoritmo para depois que isso é feito para a raiz da árvore.
    - - constrói um heap por meio de inserções sucessivas de uma nova chave em um heap previamente construído
        
        anexe um novo nó com a chave K após a última folha do heap existente
        
        Compare K com a chave de seu pai: se esta for maior ou igual a K, pare
        
        caso contrário, troque essas duas chaves e compare K com seu novo pai.
        
        Essa troca continua até K não ser maior que seu último pai ou atingir a raiz
  - - - Troque a chave da raiz pela última chave K do heap.
        
        Diminua o tamanho do heap em 1.
        
        “Heapificar” a árvore menor peneirando K na árvore exatamente da mesma maneira que fizemos no algoritmo de construção de heap de baixo para cima.
      - Eficiência da exclusão
        
        O(log n)
- - - - Tanto no pior caso quanto no caso médio