Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps and Heapsort - Coggle Diagram

- - - - operações
        
        achar um item com a maior prioridaede
        
        deletar um item com a maior prioridade
        
        adicionar um novo item
  - - - todos os níveis da árvore estão necessáriamente completos (menos, talvez, o último)
      - as chaves dos pais sempre são maiores que seus filhos
    - - existem exatamente uma árvore binária com n nós. altura = chão(log2 n)
      - a raiz sempre tem o maior elemento
      - um nó de um heap com todos seus descendentes é também um heap
      - pordemos armazenar um array de forma que:
        
        chão(n/2) = parental nodes
        
        teto(n/2) = leaves
  - - - conferimos de cima para baixo se parental>=child, se não for, trocamo os dois e repetimos
    - - colocamos um novo nó na última folha. comparamos com o parental, se for maior trocamos os dois e repetimos
      - menos eficiente
- - - - os elementos são deletados em ordem decrescente
  - - - eficiência correspondente ao mergesort