Please enable JavaScript.

Coggle requires JavaScript to display documents.

M10 - Coggle Diagram

- - - - 1º: Shape property: A binary tree é completa (Completada de cima para baixo, da direita para a esquerda).
      - 2º: A key de cada nó é maior ou igual às keys das suas children.
    - - 1º: Existe exatamente uma árvore binária completa com N nós. A sua height é igual a log2n.
      - 2º: A root de uma heap sempre contém seu maior elemento.
      - 3º: Um nó de uma heap considerado com todos os seus decendentes também é uma heap.
      - 4º: Heaps podem ser armazenadas em arrays, mas geralmente deixa-se a posição 0 do array vazia ou usando uma sentinela. Os nós que tem children ficam na primeira metade do array e as leaves ficam na segunda metade. As children de uma key com posição i estarão nas posições 2i e 2i + 1.
    - - 1º: Bottom-up (Mais eficiente): Inicializa o array com a ordem dada pelo usuário do programa e vai fazendo as checagens e trocas quando necessário.
      - 2º: Top-down: Insere elementos em uma heap já criada fazendo comparações e mudanças quando necessário.
    - - Compete com mergesort em questão de eficiência e é feita em 2 passos:
        
        1º: Construção da heap
        
        2º: Deleção de n-1 elementos da heap. A deleção de heap retorna o maior elemento da heap, que pode ser inserido na última posição de um array e no final de todas as deleções teremos um array ordenado em ordem crescente.