Podría pensarse que el coste de la creación de un montículo (heap) con n elementos está en O(n log n), dado que hay que insertar n datos y cada inserción, en el caso peor, sería O(log n).
Pues bien, haciendo el “cálculo fino” (penúltima transparencia de este fichero) puede demostrarse que realmente ese coste está en O(n).
Puede verse también, en detalle, en el libro [CLRS09, pp. 151-169].