Enunciado:
A ordem de crescimento da operação BUILD-MAX-HEAP era estimada em O(n lg n), porém fazendo uma analiza melhor pode-se mostrar que esta operação tem ordem de crescimento mais restrita igual a O(n). Por que o mesmo não se aplica a funcao HEAPSORT, sabendo que esta tem um comportamento parecido ao da operação BUID-MAX-HEAP?
A resposta correta para esta interrogação é:

A) A operação MAX-HEAPIFY é chamada apenas 1 vez no procedimento BUILD-MAX-HEAP, enquanto é executada n vezes na função HEAPSORT.
B) A altura da árvore na qual se aplica a operação MAX-HEAPIFY diminui  a cada interação tanto na operação BUILD-MAX-HEAP quanto na função HEAPSORT. Portanto, pode-se mostrar para ambos casos que a ordem de crescimento mais restrita é O(n).
C) A operação MAX-HEAPIFY é chamada, a cada interação, em subarvores com alturas diferentes (de 1 ate altura maxima do heap) no procedimento BUILD-MAX-HEAP; assim MAX-HEAPIFY é executada muitas vezes com alturas pequenas (nas folhas - maioria) e executada pouquissimas vezes com altura lg n (perto da raiz - minoria). Já na função HEAPSORT ocorre o contrário, a operação MAX-HEAPIFY é executada muitas vezes (para as folhas) partindo da raiz (altura lg n), e poucas vezes (nos próximos à raiz) partindo da raiz (altura pequena); assim a altura lg n contribui muito, fazendo a ordem de crescimento manter-se restrita em O(n lg n).
D) Na verdade não é correto afirmar que a operação BUILD-MAX-HEAP tem ordem de crescimento mais restrita igual a O(n), pois a operação MAX-HEAPIFY - que possui ordem de crescimento lg n - é chamada n vezes na construção do heap. Assim a ordem de crescimento mais restrita da operação BUILD-MAX-HEAP é O(n lg n).
E) NDA

Autor(a): Fabio Batista Gomes (RA 022256)