Aula 04

---

Representação de árvores em vetores

• a[1…m] representa uma árvore
• Dizemos que para qualquer nó/índice i, o 2i é o filho esquerdo de i
• E para qualquer nó i, o 2i é o filho direito de i.
• i/2 é o pai de i.
• Se i não tem pai, ele é a raiz.
• i tem filho esquerdo se 2i <= m
• i tem filho direito 2i+1 <= m
  • rever essas duas afirmações, não entendi direito
• Cada nível tem os nós em $$ 2^p, 2^p+1, 2^p + 2, …, 2^{p+1}-1 $$
• Qual o nível de nó i :

$$ 2^p <= i < 2^{p+1} \ \ p<= lg(i) < p+1 \longrightarrow p = floor(lg(i)). $$

Portanto, a árvore tem 1 + lg(m) níveis

Altura

• A altura de um nó i é o caminho principal até uma folha
  • A altura de um nó i é $ floor(lg(\frac{m}{i})) $

---

Max-Heap

• Um vetor [1..m] é um max-heap se $$ a[\frac{i}{2}] >= a[i], \forall i=2,3,..m $$

• Função básica de um max-heap : sink

  private static void sink (int p, int m, int[] a) {
      int f = 2*pai; //filho esquerdo
      while (f <= m) { // para quando eu chego numa folha
          if (f < m && a[f] < a[f+1])  //se o filho existe e for maior que o irmão...
              f++;
         	if (a[f] <= a[p])  // se os filhos forem menores que o filho, show.
              break;
          int x = a[p]; a[p] = a[f]; a[f] = x; // troca o pai com o maior filho
  
      }
  }
  
  /*
  	Eu poderia ter usado um método comparable na linha 4. o compareTo é um método do java que alguns tipos de dados possuem
  */
  

Consumo de tempo

• $O(log(M))$

Objetos Comparáveis

$$ Obj1.compareTo(obj2) = \begin{array}{11} < 0,\ se \ obj1<obj2 \ = 0, \ se\ obj1=obj2 \ > 0, \ se\ obj1> obj2 \end{array} $$

---