# 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**

  ```java
  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}
$$