He detectado que algunos siguen pensando que el coste de la creación de un montículo (heap) con n elementos está en O(n log n). Pues bien, haciendo el “cálculo fino” (penúltima transparencia del siguiente fichero) puede verse que realmente ese coste está en O(n).

Puede verse en detalle en el libro [CLRS09, pp. 151-169].