Análise do Algoritmo
O tempo de execução para qualquer nó i é ?(1), o tempo para corrigir o relacionamento entre A[i], A[Esquerda(i)] e A[Direita (i)], mais o tempo para executar Heapify sobre uma das sub-árvores filhas. E, cada sub-árvore filha têm tamanho de no máximo 2n/3 (o pior caso ocorre quando a última fileira da árvore está exatamente cheia até a metade).
Assim, T(n) ? T(2n/3) + ?(1)
Alternativamente, Heapify requer O(h) onde h é a altura do nó ao qual Heapify é aplicada.