MO417 - Questão para a prova oral

Número: 038

Enunciado:
O algoritmo abaixo é um algoritmo de ordenação que utiliza a estrutura de dados conhecida como fila de prioridade. Dê a complexidade de tempo no pior caso para uma entrada A[l .. r] de elementos inteiros.

	Sort(A, l, r)
	{
		PQInit()
		for k <- l to r
			do PQInsert(A[k])
		for k <- r downto l
			do A[k] <- PQdelmax()
	}
	

Onde:

PQInit()

apenas inicializa a fila de prioridades em tempo constante,

PQInsert(A[k])

insere um elemento na fila de prioridades, e

PQdelmax()

remove o item de maior prioridade da fila. Todas as funções citadas são implementadas com o uso de uma estrutura de heap.

1. O(n)
2. O(n lg(n))
3. O(n²)
4. O(n³)
5. NDA

Autor(a): Jonathas Campi Costa - RA: 085380