Questão 769228

• Banca: CESPE / CEBRASPE
• Órgão: Banco da Amazônia
• Ano: 2012
• Provas: CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

O acréscimo de um elemento em um heap pode mudar o nó raiz, dependendo do seu valor.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• O heap é uma árvore binária em que:
  A diferença máxima de altura entre os nós folha é de um nível;
  Os nós do nível mais profundo são preenchidos da esquerda para a direita;
  Todo nó deve armazenar uma chave maior do que as dos seus filhos
  
  Logo, pode haver mudança na raiz.
• O heap é um tipo particular de árvore binária com as seguintes propriedades:
  1. O valor de um nó não pode ser menor que o valor dos nós de suas subárvores (seus filhos);
  2. A árvore é perfeitamente balanceada;
  Portanto se for inserido um nó cujo valor é maior que o da raiz, o nó recém-inserido será a nova raiz.
  
  Vejam um exemplo: no heap a seguir (árvore superior esquerda), deseja-se inserir o número 441. Observe como os nós do heap são deslocados (shift) para que o nó recém-inserido assuma a posição correta (nesse caso, ele tornando-se a raiz) e restaurando as propriedades da estrutura de dados.
  
   
• Animação sobre heap: http://www.youtube.com/watch?v=QdRL3XLyiVc

• Força Guerreiro!!!!!!