OK. Entiendo. Hay que comparar el costo de obtener el mínimo con búsqueda a pedal en un arreglo, frente extraer el primer elemento del heap (es decir O(1) frente a O(n)).
Otra comparación que es interesante es la del costo de construcción con los diferentes métodos. A mi me está dando que la manera ineficiente (inserción sucesiva de elementos) en lugar de ser O(n log n), en realidad es O(n). Esto parece ser porque la estimación O(n log n), que considera costo de inserción O(log n) y n operaciones es de peor caso, pero en realidad el costo promedio de una inserción es O(1) (como está en las transparencias de clase) con lo que la construcción es de costo O(n). La implementación eficiente también es O(n) y solo difieren en la constante que determina la pendiente del crecimiento lineal con los datos. Por suerte la implementación eficiente está un poco por debajo.
Saludos y gracias!