Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heap e HeapSort - Coggle Diagram

- - - - Os nós que são pais se localizam nas primeiras piso(n/2) posições, enquanto os nós que são folhas ficam nas ultimas teto(n/2) posições
      - Os filhos de um nó pai na posição i (1<= i <= piso(n/2)) vão estar na posição 2i e 2i + 1, já se estamos atrás do índice do pai de um filho em j (2<= j <= n), dizemos que que esse índice é igual a piso(j/2)
        
        Ou seja, cada elemento i, da primeira metade do array, é maior ou igual a 2i e 2i+1
      - Implementação como array é a mais eficiente
- - - - E então verificamos a dominância parental do elemento na nova posição... E assim vai até o elemento ser colocado como folha ou até ele encontrar filhos menores
        
        Deve ser usado quando sabemos todos os elementos que vão estar na heap
      - Note que esse processo começa com o ultimo pai e o algoritmo para quando essa verificação for feita para a raiz
    - - Porém no pior caso pode chegar a BigTheta(n)
  - - - A cada inserção colocamos o novo elemento como uma folha e depois levamos esse elemento para sua devida posição usando um método que está incluso na construção Botton-up, nessa construção nós fazemos uma verificação para cada pai para saber se ele está bem posicionado (caso não, então o método ajusta a sua posição), no Top-down fazemos essa mesmo processo apenas para o elemento que foi inserido
        
        Deve ser usado quando NÃO sabemos todos os elementos que vão estar na heap