SóProvas


ID
1561498
Banca
Marinha
Órgão
Quadro Complementar
Ano
2013
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Em relação às listas de prioridades, qual das seqüências abaixo corresponde a um HEAP?

Alternativas
Comentários
  • O gabarito é a letra E.

     

    Heap é uma árvore-binária (ou seja, cada nó possui dois filhos) onde cada nó possui um determinado valor e onde o valor do pai é sempre maior ou igual que o dos filhos (sendo chamada de max heap) ou sempre menor ou igual que o dos filhos (sendo chamada de min heap). A raiz, portanto, deve ser o maior elemento.

     

    Uma Heap pode ser representada simplesmente por um array. Para ir preenchendo o array, imagine que se vá preenchendo nível a nível (nos níveis da árvore), preenchendo cada nível da esquerda para a direita.

     

    Nessa questão, resolvi fazendo o caminho inverso: construí a árvore a partir do array e verifiquei se satisfazia as condições da Heap.

     

    A - Raiz: 184

         Nível 1: 170 e 180

         Nível 2: 94 e 182 (filhos de 170) => errado, pois 182 é maior que 170

     

    B - Raiz: 95 => errado, pois o maior elemento do array é 98, que deveria ser a raiz

     

    C - Raiz: 92

          Nível 1: 85 e 90

          Nível 2: 47 e 91 (filhos de 85) => errado, pois 91 é maior que 85

     

    D - Raiz: 33

          Nível 1: 32 e 28

          Nível 2: 31 e 26 (filhos de 32) e 29 e 25 (filhos de 28) => errado, pois 29 é maior que 28

     

    E - Raiz: 190

          Nível 1: 120 e 156

          Nível 2: 78 e 56 (filhos de 120) e 132 e 140 (filhos de 156)

          Nível 3: 66 (filho de 78)