Vamos analisar cada uma das afirmações: I - Uma vez que o heap é implementado como árvore binária de busca essencialmente completa, o custo computacional para sua construção é O(n log n). Falso. A construção de um heap pode ser feita em O(n) usando o método de "heapify". II - A implementação de heaps utilizando-se vetores é eficiente em tempo de execução e em espaço de armazenamento, pois o pai de um elemento na posição i está armazenado na posição 2i+1. Falso. Na verdade, o pai de um elemento na posição i está na posição (i-1)/2 (para heaps baseados em zero). III - O custo computacional para recuperar de forma ordenada os n documentos mais relevantes armazenados em um heap de tamanho n é O(m log n). Verdadeiro. Para recuperar os n documentos mais relevantes, você precisa remover o elemento do heap n vezes, o que resulta em O(n log n) no total, mas se considerarmos m como o número de documentos a serem recuperados, a afirmação é correta. IV - Determinar o documento com maior valor de relevância armazenado em um heap implica custo computacional O(1). Verdadeiro. O maior elemento em um heap (max-heap) está sempre na raiz, que pode ser acessada em O(1). Agora, vamos ver quais itens são verdadeiros. Os itens III e IV estão corretos. Portanto, a alternativa correta que contém todos os itens verdadeiros é: c) III e IV.