Questão 238300

• Banca: CESPE / CEBRASPE
• Órgão: ABIN
• Ano: 2010
• Provas: CESPE - 2010 - ABIN - Oficial Técnico de Inteligência - Área de Suporte a Rede de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

A respeito dos métodos de ordenação, pesquisa e hashing, julgue
os seguintes itens.

A estrutura de dados heap, que é eficiente para a implementação do método de ordenação heapsort, consiste em uma árvore binária completa e sua implementação mais simples ocorre na forma de array.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• O heapsort utiliza uma estrutura de dados chamada heap (monte), para ordenar os elementos à medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada, lembrando-se sempre de manter a propriedade de max-heap.

  A heap pode ser representada como uma árvore (uma árvore binária com propriedades especiais^[2]) ou como um vetor. Para uma ordenação crescente, deve ser construído um heap máximo (o maior elemento fica na raiz). Para uma ordenação decrescente, deve ser construído um heap mínimo (o menor elemento fica na raiz).

  Referência: http://pt.wikipedia.org/wiki/Heapsort

• Minha dúvida está em:
  
  "...consiste em uma árvore binária completa..."
  
  pelo que vi, a definição de arvore completa depende de autor.
  alguns dizem que completa deve ser estritamente binária (cada nó tem 0 ou 2 filhos, não pode ter 1), e nesse caso, heap não é completa...
• Fiquei com a mesma dúvida da laura.
• Pessoal, vejam a relação entre Heapsort e Árvore Binária:
  
  http://www.das.ufsc.br/~camponog/Disciplinas/DAS-9003/slides_CLR/l8-trees-heaps.pdf
• Passando as informações do link que o  Rogério enviou:
  
  

   

  Heaps
  - Um heap (binário) é uma estrutura de dados que pode ser vista como uma  arvore binária completa.
  - Cada nó da árvore corresponde a um elemento do vetor que armazena o valor do nó.
  - A árvore é completa em todos os níveis com exceção do nível mais baixo, o qual é completado da esquerda para a direita.
• Prezados,
  
  Segundo André Backes, em seu livo Estrutura de dados descomplicada, o algoritmo heapsort, também conhecido como ordenação por heap, é um algoritmo de ordenação bastante sofisticado e que compete em desempenho com o quicksort. A ideia deste algoritmo é transformar o array de dados em uma estrutura do tipo heap, isto é , uma árvore binária completa. Essa estrutura permite a recuperação e remoção eficiente do elemento de maior valor do array. Desse modo podemos repetidamente "remover" o maior elemento da heap, construindo assim o array ordenado de trás pra frente.
  
  Portanto a questão está correta.
  

• acho que era pra ser quase completa, não?