Questão 1208254

• Banca: CESPE / CEBRASPE
• Órgão: TJ-SE
• Ano: 2014
• Provas: CESPE - 2014 - TJ-SE - Analista Judiciário - Análise de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

        Um sistema de controle distribui os processos para os juízes de um tribunal utilizando critérios de prioridade associados a cada processo, de modo que novos processos podem ser analisados pelos juízes enquanto outros aguardam análise.

Considerando essas informações, julgue os itens a seguir, acerca dos tipos básicos de estruturas de dados e de operações sobre estruturas de dados.

Caso a implementação da fila de prioridades dos processos em questão seja realizada por meio de min-heap, e a distribuição dos processos seja efetuada selecionando-se e removendo-se o processo que se encontra na raiz, é correto afirmar que o processo selecionado será o de maior prioridade.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• Max-heap

  Em termos um tanto vagos, um max-heap (ou árvore hierárquica) é uma árvore binária quase completa em que cada pai é maior ou igual que qualquer de seus filhos. (Se trocássemos "maior ou igual" por "menor ou igual" teríamos um min-heap.) 

  Se A[1..n] é um max-heap, é muito fácil encontrar um elemento máximo do vetor: A[1] é máximo. fonte: http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/heap.html
  
  A questão se referia ao min-heap, ou seja, a implementação contraria da explicação acima o que acarreta em uma raiz de menor valor tornando a questão errada.

• Caso a implementação da fila de prioridades dos processos em questão seja realizada por meio de min-heap, e a distribuição dos processos seja efetuada selecionando-se e removendo-se o processo que se encontra na raiz, é correto afirmar que o processo selecionado será o de menor ( ao invés de maior) prioridade.
  

• min-heap --> raiz de menor valor, filhos de maior valor
  
  max-heap --> raiz de MAIOR valor, filhos de menos valor
  
  Desta foma, para que o processo que se encontra na raiz tivesse maior prioridade deveria ter sido usado max-heap.

• A eliminação no heap raiz indica que os demais subproblemas, ou os elementos maiores foram resolvidos antes do menor (raiz)

• Força Guerreiro!!!!!!