Insertar un elemento en un montón toma O (log n). ¿Aún si insertamos n elementos en el montón, resulta ser O (n)?

Sí, tiene razón en que insertar un elemento en el montón lleva tiempo O (log). Todavía tenemos un algo en el que el elemento n / max heap toma O (n) tiempo.

Su duda surge debido a dos métodos para construir un montón mínimo / máximo. Uno toma O (nlogn) tiempo (como su duda es) mientras que el otro toma O (n).

Discutamos ambos métodos conceptualmente. Digamos que queremos construir un montón mínimo de n elementos: –

El primer método es Heapify de arriba hacia abajo , en este método tomamos elementos uno por uno y aplicamos el proceso de heapify para que en cada inserción se cumplan las propiedades mínimas del montón.

Dado que la inserción de un elemento lleva mucho tiempo. Por lo tanto, insertar n elementos llevará tiempo O (nlogn).

El proceso de Heapify de arriba hacia abajo llevará tiempo O (nlogn). {en promedio / peor de los casos}.

El segundo método es Heapify de abajo hacia arriba , en este método simplemente tomamos todos los elementos y los insertamos en el árbol binario casi completo. Esto llevará tiempo O (n).

Ahora satisfaceremos la propiedad de almacenamiento dinámico mínimo de la parte inferior a la más alta moda. Esto se llama Heapify de abajo hacia arriba.

Dado que tenemos n / 2 nodos de hoja en un árbol binario casi completo con n nodos. Por lo tanto, estos elementos n / 2 tendrán cero comparaciones e intercambios. Y para los n / 2 nodos restantes, para cada nivel, el número de swaps será tal que obtendremos un GP decreciente. Esto tomará el número total de intercambios del orden de O (n).

Ahora el número total de comparaciones en este proceso es el doble del número total de intercambios.

Por lo tanto, las comparaciones también llevarán tiempo O (n).

Ahora el tiempo total en Bottom-Up Heapify será: –

O (n) {insertar todos los n elementos en el árbol} + O (n) {para intercambios} + O (n) {para comparaciones}

Que es asintóticamente equivalente a O (n), y este método de acumulación ascendente se llama método Build Heap.

Por lo tanto, la construcción de un montón mínimo / máximo con el método Build Heap llevará O (n) tiempo.

Insertar un elemento lleva tiempo O (lg n) en un montón. Por lo tanto, insertar n elementos tomará O (n lg n) en el peor de los casos.

Pero cuando estamos construyendo un montón, no necesitamos insertar cada elemento individualmente y, por lo tanto, podemos mejorar el tiempo hasta O (n). Tim ya ha explicado el algoritmo.