Question

As filas de prioridades (heaps) são estruturas de dadosimportantes no projeto de algoritmos. Em especial, heapspodem ser utilizados na recuperação de informaçãoem grandes bases de dados constituídos por textos.Basicamente, para se exibir o resultado de uma consulta,os documentos recuperados são ordenados de acordocom a relevância presumida para o usuário. Uma consultapode recuperar milhões de documentos que certamentenão serão todos examinados. Na verdade, o usuárioexamina os primeiros m documentos dos n recuperados,em que m é da ordem de algumas dezenas.Considerando as características dos heaps e suaaplicação no problema descrito acima, avalie asseguintes afirmações.I. Uma vez que o heap é implementado comouma árvore binária de pesquisa essencialmentecompleta, o custo computacional para suaconstrução é O(n log n).II. A implementação de heaps utilizando-se vetoresé eficiente em tempo de execução e em espaçode armazenamento, pois o pai de um elementoarmazenado na posição i se encontra armazenadona posição 2i+1.III. O custo computacional para se recuperarde forma ordenada os m documentos maisrelevantes armazenados em um heap detamanho n é O(m log n).IV. Determinar o documento com maior valor derelevância armazenado em um heap tem custocomputacional O(1).Está correto apenas o que se afirma emA I e II.B II e III.C III e IV.D I, II e IV.E I, III e IV.

#ENADE

Answer 1

A resposta correta é a de letra (C) III e IV.

A primeira afirmativa está incorreta pois o Heap não é implementando como uma árvore binária, ele é a própria arvore porém não funciona para fins de pesquisa pois eles não se enquadra nas propriedades necessárias para isso.

Já a segunda também está incorreta pois a posição do i está localizada incorretamente (que é considerado o pai do elemento), a ordem verdadeira é feita da seguinte forma:  (i−1)/2.

Espero ter ajudado! Bons Estudos!