Tempo de Execução
O tempo requerido por Heapify sobre um nó de altura h é O(h). De modo que nós podemos expressar o custo total de Build-Heap como
? h=0 à lgn ?n / 2h+1? O(h) = O( n ? h=0 à lgn h/ 2h )
e, ? h=0 à ? h/ 2h = (1/2) / (1 - 1/2)2 = 2
Portanto, O( n ? h=0 à lgn h/ 2h ) = O(n)
Assim, pode-se construir uma heap de um vetor aleatório em um tempo linear.