Um heap binário é um arranjo que pode ser visualizado como uma árvore binária

ENADE 2021 - QUESTÃO DISCURSIVA 05 - BACHARELADO Um heap binário é um arranjo que pode ser visualizado como uma árvore binária, sendo que ca...

ENADE 2021 - QUESTÃO DISCURSIVA 05 - BACHARELADO

Um heap binário é um arranjo que pode ser visualizado como uma árvore binária, sendo que cada nó da árvore corresponde a um elemento do arranjo, como pode ser observado na figura a seguir.

Percebe-se que existem dois tipos de heaps: heaps máximo e heaps mínimo. O heap máximo é uma estrutura de dados que possibilita a consulta ou extração de forma eficiente do maior elemento de uma coleção. A propriedade de heapmáximo especifica que um nó filho (no código calculado pelas funções left e right) tem sempre armazenado um valor menor ou igual ao seu pai.

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. 

Introduction to Algorithms. 3. ed. MIT Press and McGraw-Hill. 

p. 131-161, 2009 (adaptado).

Considerando a implementação a seguir, o heapify é uma função auxiliar para reorganizar o arranjo (garantindo a propriedade de heapmáximo em uma determinada posição do arranjo) e buildHeap é uma função que usa heapifypara reorganizar todas as posições do arranjo (garantindo a propriedade de heap máximo para todos os elementos).

De acordo com as informações apresentadas, faça o que se pede nos itens a seguir.

a) Como ficará o arranjo int a[ ] = {2, 5, 8 ,13, 21, 1, 3, 34} após a execução da função buildHeap(a, 8). (valor: 5,0 pontos)

b) Apresente a complexidade de tempo no pior caso para a função heapify, use a notação O ou . (valor: 5,0 pontos)

QUESTÃO ANTERIOR:

- A maioria dos governos de todo o mundo fecharam temporariamente as instituições educacionais na tentativa de conter a pandemia da Covid-19.

PADRÃO DE RESPOSTA:

(EM BREVE...)

PRÓXIMA QUESTÃO:

- Quando um computador é multiprogramado, ele geralmente tem múltiplos processos ou threads que competem pela CPU ao mesmo tempo.

QUESTÃO DISPONÍVEL EM:

- Prova ENADE 2021 Ciência da computação (licenciatura e bacharelado) com Gabarito