algorithm - ¿Cómo puede construir un montón una complejidad de tiempo O(n)?

min heap c++ (14)

¿Puede alguien ayudar a explicar cómo construir un montón puede ser complejidad O?

La inserción de un elemento en un montón es O(log n) , y el inserto se repite n / 2 veces (el resto son hojas y no puede violar la propiedad del montón). Entonces, esto significa que la complejidad debería ser O(n log n) , creo.

En otras palabras, para cada elemento que "heapify", tiene el potencial de tener que filtrar hacia abajo una vez para cada nivel para el montón hasta ahora (lo que es niveles de registro n).

¿Qué me estoy perdiendo?

Intuitivamente:

"La complejidad debe ser O (nLog n) ... para cada elemento que" heapificamos ", tiene el potencial de tener que filtrar hacia abajo una vez para cada nivel para el montón hasta ahora (que es niveles de registro n)".

No exactamente. Su lógica no produce un límite estricto: sobreestima la complejidad de cada heapify. Si se construye de abajo hacia arriba, la inserción (heapify) puede ser mucho menor que O(log(n)) . El proceso es el siguiente:

(Paso 1) Los primeros n/2 elementos van en la fila inferior del montón. h=0 , por lo que no se necesita heapify.

(Paso 2) Los siguientes n/2 ² elementos van en la fila 1 desde la parte inferior. h=1 , heapify filtros 1 nivel hacia abajo.

(Paso i ) Los siguientes elementos n/2 ⁱ van en la fila i hacia arriba desde la parte inferior. h=i , heapify filtros i niveles hacia abajo.

(Paso log (n) ) El último n/2 ^{log ₂ (n)} = 1 elemento va en la fila log(n) hacia arriba desde la parte inferior. h=log(n) , heapify filtra los niveles de log(n) hacia abajo.

AVISO: después del paso uno, la 1/2 de los elementos (n/2) ya están en el montón, y ni siquiera tuvimos que llamar a heapify una vez. Además, tenga en cuenta que solo un elemento, la raíz, incurre en realidad en la complejidad de log(n) .

Teóricamente

El Total de pasos N para construir un montón de tamaño n , se puede escribir matemáticamente.

En la altura i , hemos demostrado (arriba) que habrá n/2 ⁱ⁺¹ elementos que deben llamarse heapify, y sabemos que heapify en la altura i es O(i) . Esto da:

La solución para la última suma se puede encontrar tomando la derivada de ambos lados de la conocida ecuación de serie geométrica:

Finalmente, al insertar x = 1/2 en la ecuación anterior se obtiene 2 . Al enchufar esto en la primera ecuación se obtiene:

Por lo tanto, el número total de pasos es de tamaño O(n)

"El límite de tiempo lineal de la acumulación Heap, puede mostrarse calculando la suma de las alturas de todos los nodos de la pila, que es el número máximo de líneas discontinuas. Para el árbol binario perfecto de altura h que contiene N = 2 ^ ( h + 1) - 1 nodos, la suma de las alturas de los nodos es N - H - 1. Por lo tanto, es O (N) ".

@bcorso ya ha demostrado la prueba del análisis de complejidad. Pero por el bien de aquellos que aún están aprendiendo análisis de complejidad, tengo esto para agregar:

La base de su error original se debe a una mala interpretación del significado de la declaración, "la inserción en un montón lleva tiempo O (log n)". La inserción en un montón es de hecho O (log n), pero hay que reconocer que n es el tamaño del montón durante la inserción .

En el contexto de insertar n objetos en un montón, la complejidad de la inserción ith es O (log n_i) donde n_i es el tamaño del montón como en la inserción i. Solo la última inserción tiene una complejidad de O (log n).

Básicamente, el trabajo se realiza solo en nodos sin hojas mientras se construye un montón ... y el trabajo realizado es la cantidad de intercambio hacia abajo para satisfacer la condición del montón ... en otras palabras (en el peor de los casos) la cantidad es proporcional a la altura del nodo ... todo en toda la complejidad del problema es proporcional a la suma de alturas de todos los nodos no hoja ... que es (2 ^ h + 1 - 1) -h-1 = nh-1 = En)

Como sabemos, la altura de un montón es log (n) , donde n es el número total de elementos. Lo representamos como h
Cuando realizamos la operación de heapify, entonces los elementos en el último nivel ( h ) no se moverán ni un solo paso.
El número de elementos en el segundo último nivel ( h-1 ) es 2 ^h-1 y pueden moverse a un nivel máximo de 1 (durante el proceso de heapify).
De manera similar, para el nivel i tenemos niveles 2 ⁱ que pueden mover posiciones altas.

Por lo tanto, el número total de movimientos = S = 2 ^h * 0 + 2 ^h-1 * 1 + 2 ^h-2 * 2 + ... 2 ⁰ * h

S = 2 ^h {1/2 + 2/2 ² + 3/2 ³ + ... h / 2 ^h } ----------------------- -------------------------- 1
Esta es la serie AGP , para resolver esta división ambos lados por 2.
S / 2 = 2 ^h {1/2 ² + 2/2 ³ + ... h / 2 ^{h + 1} } ----------------------- -------------------------- 2
restando la ecuación 2 de 1 da
S / 2 = 2 ^h { 1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h + h / 2 ^{h + 1} }
S = 2 ^{h + 1} { 1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h + h / 2 ^{h + 1} }
ahora 1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h está disminuyendo GP cuya suma es menor que 1 (cuando h tiende a infinito, la suma tiende a 1). En un análisis más detallado, tomemos un límite superior en la suma que es 1.
Esto da S = 2 ^{h + 1} {1 + h / 2 ^{h + 1} }
= 2 ^{h + 1} + h
~ 2 ^h + h
como h = log (n) , 2 ^h = n

Por lo tanto S = n + log (n)
T (C) = O (n)

Creo que hay varias preguntas enterradas en este tema:

¿Cómo implementas buildHeap para que se ejecute en tiempo O (n) ?
¿Cómo muestra que buildHeap se ejecuta en tiempo O (n) cuando se implementa correctamente?
¿Por qué no funciona esa misma lógica para hacer que la ordenación del montón se ejecute en tiempo O (n) en lugar de O (n log n) ?

A menudo, las respuestas a estas preguntas se centran en la diferencia entre siftUp y siftDown . Tomar la decisión correcta entre siftUp y siftDown es fundamental para obtener el rendimiento de O (n) para buildHeap , pero no hace nada para ayudar a comprender la diferencia entre buildHeap y heapSort en general. De hecho, las implementaciones adecuadas de buildHeap y heapSort solo usarán siftDown . La operación siftUp solo es necesaria para realizar inserciones en un montón existente, por lo que se usaría para implementar una cola de prioridad utilizando un montón binario, por ejemplo.

He escrito esto para describir cómo funciona un montón máximo. Este es el tipo de almacenamiento dinámico que se usa normalmente para la clasificación de almacenamiento dinámico o para una cola de prioridad donde los valores más altos indican una prioridad más alta Un montón mínimo también es útil; por ejemplo, al recuperar elementos con claves enteras en orden ascendente o cadenas en orden alfabético. Los principios son exactamente los mismos; simplemente cambia el orden de clasificación.

La propiedad de montón especifica que cada nodo en un montón binario debe ser al menos tan grande como sus dos hijos. En particular, esto implica que el elemento más grande del montón está en la raíz. La clasificación hacia abajo y hacia arriba son esencialmente la misma operación en direcciones opuestas: mueva un nodo ofensivo hasta que satisfaga la propiedad de montón:

siftDown intercambia un nodo que es demasiado pequeño con su hijo mayor (moviéndolo hacia abajo) hasta que sea al menos tan grande como los dos nodos debajo de él.
siftUp intercambia un nodo que es demasiado grande con su padre (por lo tanto, lo mueve hacia arriba) hasta que no sea más grande que el nodo que está sobre él.

El número de operaciones requeridas para siftDown y siftUp es proporcional a la distancia que el nodo puede tener que mover. Para siftDown , es la distancia desde la parte inferior del árbol, por lo que siftDown es costoso para los nodos en la parte superior del árbol. Con siftUp , el trabajo es proporcional a la distancia desde la parte superior del árbol, por lo que siftUp es costoso para los nodos en la parte inferior del árbol. Aunque ambas operaciones son O (log n) en el peor de los casos, en un montón, solo hay un nodo en la parte superior, mientras que la mitad de los nodos se encuentran en la capa inferior. Entonces, no debería ser demasiado sorprendente que si tenemos que aplicar una operación a cada nodo, preferiríamos siftDown sobre siftUp .

La función buildHeap toma una matriz de elementos sin clasificar y los mueve hasta que todos satisfacen la propiedad de montón, lo que produce un montón válido. Hay dos enfoques que se podrían tomar para buildHeap utilizando las operaciones siftUp y siftDown que hemos descrito.

Comience en la parte superior del montón (el comienzo de la matriz) y llame a siftUp en cada elemento. En cada paso, los elementos previamente seleccionados (los elementos anteriores al elemento actual en la matriz) forman un montón válido, y al seleccionar el siguiente elemento, se coloca en una posición válida en el montón. Después de seleccionar cada nodo, todos los elementos satisfacen la propiedad de montón.
O bien, vaya en la dirección opuesta: comience al final de la matriz y muévase hacia atrás hacia el frente. En cada iteración, tamiza un elemento hacia abajo hasta que se encuentre en la ubicación correcta.

Ambas soluciones producirán un montón válido. La pregunta es: ¿qué implementación para buildHeap es más eficiente? Como era de esperar, es la segunda operación que utiliza siftDown .

Sea h = log n la altura del montón. El trabajo requerido para el enfoque siftDown está dado por la suma

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

Cada término en la suma tiene la distancia máxima que un nodo en la altura dada tendrá que moverse (cero para la capa inferior, h para la raíz) multiplicado por el número de nodos en esa altura. En contraste, la suma para llamar a siftUp en cada nodo es

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

Debe quedar claro que la segunda suma es mayor. El primer término solo es hn / 2 = 1/2 n log n , por lo que este enfoque tiene complejidad en el mejor de los casos (n log n) . Pero, ¿cómo probamos que la suma para el enfoque siftDown es O (n) ? Un método (hay otros análisis que también funcionan) es convertir la suma finita en una serie infinita y luego usar la serie de Taylor. Podemos ignorar el primer término, que es cero:

Si no está seguro de por qué cada uno de esos pasos funciona, aquí hay una justificación del proceso con palabras:

Los términos son todos positivos, por lo que la suma finita debe ser más pequeña que la suma infinita.
La serie es igual a una serie de potencia evaluada en x = 1/2 .
Esa serie de potencias es igual a (una vez constante) la derivada de la serie de Taylor para f (x) = 1 / (1-x) .
x = 1/2 está dentro del intervalo de convergencia de esa serie de Taylor.
Por lo tanto, podemos reemplazar la serie de Taylor con 1 / (1-x) , diferenciar y evaluar para encontrar el valor de la serie infinita.

Como la suma infinita es exactamente n , concluimos que la suma finita no es mayor y, por lo tanto, es O (n) .

La siguiente pregunta es: si es posible ejecutar buildHeap en tiempo lineal, ¿por qué la ordenación de heap requiere tiempo O (n log n) ? Bueno, el tipo de pila consiste en dos etapas. Primero, llamamos a buildHeap en la matriz, que requiere O (n) tiempo si se implementa de manera óptima. La siguiente etapa es eliminar repetidamente el elemento más grande del montón y colocarlo al final de la matriz. Debido a que eliminamos un elemento del montón, siempre hay un espacio abierto justo después del final del montón donde podemos almacenar el elemento. Por lo tanto, la ordenación de pilas logra un orden ordenado al eliminar sucesivamente el siguiente elemento más grande y colocarlo en la matriz comenzando en la última posición y moviéndose hacia el frente. Es la complejidad de esta última parte la que domina en el ordenamiento de pilas. El bucle se ve así:

for (i = n - 1; i > 0; i--) { arr[i] = deleteMax(); }

Claramente, el bucle se ejecuta O (n) veces ( n - 1 para ser precisos, el último elemento ya está en su lugar). La complejidad de deleteMax para un montón es O (log n) . Normalmente se implementa eliminando la raíz (el elemento más grande que queda en el montón) y reemplazándolo con el último elemento del montón, que es una hoja, y por lo tanto uno de los elementos más pequeños. Es casi seguro que esta nueva raíz violará la propiedad del montón, por lo que debe llamar a siftDown hasta que la vuelva a colocar en una posición aceptable. Esto también tiene el efecto de mover el siguiente elemento más grande hasta la raíz. Observe que, en contraste con buildHeap donde la mayoría de los nodos estamos llamando a siftDown desde la parte inferior del árbol, ahora estamos llamando a siftDown desde la parte superior del árbol en cada iteración. Aunque el árbol se está encogiendo, no se encoge lo suficientemente rápido : la altura del árbol se mantiene constante hasta que haya eliminado la primera mitad de los nodos (cuando borra completamente la capa inferior). Luego, para el siguiente trimestre, la altura es h - 1 . Así que el trabajo total para esta segunda etapa es

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

Observe el interruptor: ahora el caso de trabajo cero corresponde a un solo nodo y el caso de trabajo h corresponde a la mitad de los nodos. Esta suma es O (n log n) al igual que la versión ineficiente de buildHeap que se implementa usando siftUp. Pero en este caso, no tenemos otra opción ya que estamos tratando de ordenar y requerimos que el siguiente elemento más grande se elimine a continuación.

En resumen, el trabajo para la ordenación de pilas es la suma de las dos etapas: O (n) tiempo para que buildHeap y O (n log n) eliminen cada nodo en orden , por lo que la complejidad es O (n log n) . Puede probar (utilizando algunas ideas de la teoría de la información) que para una ordenación basada en la comparación, O (n log n) es lo mejor que puede esperar de todos modos, por lo que no hay razón para decepcionarse o esperar que la ordenación del montón logre la O (n) límite de tiempo que buildHeap hace.

En el caso de construir el montón, comenzamos desde height, logn -1 (donde logn es la altura del árbol de n elementos). Para cada elemento presente en la altura ''h'', vamos a la altura máxima hasta (logn -h) hacia abajo.

So total number of traversal would be:- T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn))) T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn and according to the [sources][1] function in the bracket approaches to 2 at infinity. Hence T(n) ~ O(n)

Las inserciones sucesivas pueden ser descritas por:

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

Por aproximación de estornino, n! =~ O(n^(n + O(1))) n! =~ O(n^(n + O(1))) , por lo tanto, T =~ O(nlog(n))

Espero que esto ayude, la forma óptima en que O(n) está utilizando el algoritmo de acumulación de pila para un conjunto determinado (no importa el ordenamiento).

Mientras construyes un montón, digamos que estás tomando un enfoque de abajo hacia arriba.

Tomas cada elemento y lo comparas con sus hijos para verificar si el par cumple con las reglas del montón. Así, por lo tanto, las hojas se incluyen en el montón de forma gratuita. Eso es porque no tienen hijos.
Moviéndose hacia arriba, el peor de los casos para el nodo justo encima de las hojas sería 1 comparación (al máximo se compararían con una sola generación de niños)
Al avanzar, sus padres inmediatos pueden ser comparados al máximo con dos generaciones de niños.
Continuando en la misma dirección, tendrá comparaciones de log (n) para la raíz en el peor de los casos. y log (n) -1 para sus hijos inmediatos, log (n) -2 para sus hijos inmediatos y así sucesivamente.
Entonces, resumiendo todo, llegas a algo como log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ..... + 1 * 2 ^ {( logn) -1} que no es más que O (n).

Realmente me gusta la explicación de Jeremy West ... otro enfoque que es muy fácil de entender se ofrece aquí http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

ya que, el uso de buildheap depende del enfoque de heapify y shiftdown, que depende de la suma de las alturas de todos los nodos. Entonces, para encontrar la suma de altura de nodos que viene dada por S = suma de i = 0 a i = h de (2 ^ i * (hi)), donde h = logn es la altura del árbol que resuelve s, obtenemos s = 2 ^ (h + 1) - 1 - (h + 1) ya que, n = 2 ^ (h + 1) - 1 s = n - h - 1 = n - logn - 1 s = O (n), y así la complejidad del buildheap es O (n).

Sería O (n log n) si construyera el montón insertando repetidamente elementos. Sin embargo, puede crear un nuevo montón más eficientemente insertando los elementos en un orden arbitrario y luego aplicando un algoritmo para "apilarlos" en el orden correcto (dependiendo del tipo de montón, por supuesto).

Consulte http://en.wikipedia.org/wiki/Binary_heap , "Creación de un montón" para ver un ejemplo. En este caso, esencialmente se trabaja desde el nivel inferior del árbol, intercambiando los nodos padre e hijo hasta que se cumplan las condiciones del montón.

Su análisis es correcto. Sin embargo, no es apretado.

No es realmente fácil explicar por qué construir un montón es una operación lineal, es mejor que lo lea.

Un gran análisis del algoritmo se puede ver here .

La idea principal es que en el algoritmo heapify costo real de heapify no es O(log n) para todos los elementos.

Cuando se llama a heapify , el tiempo de ejecución depende de hasta qué punto un elemento puede moverse hacia abajo en el árbol antes de que finalice el proceso. En otras palabras, depende de la altura del elemento en el montón. En el peor de los casos, el elemento podría bajar hasta el nivel de la hoja.

Contemos el trabajo realizado nivel por nivel.

En el nivel inferior, hay 2^(h) nodos 2^(h) , pero no llamamos heapify en ninguno de estos, por lo que el trabajo es 0. Al siguiente nivel hay 2^(h − 1) nodos 2^(h − 1) , y cada uno puede mover hacia abajo por 1 nivel. En el 3er nivel desde la parte inferior, hay 2^(h − 2) nodos 2^(h − 2) , y cada uno puede bajar 2 niveles.

Como puede ver, no todas las operaciones de heapify son O(log n) , por eso está obteniendo O(n) .

creo que estas cometiendo un error Eche un vistazo a esto: http://golang.org/pkg/container/heap/ Construir un montón no es O (n). Sin embargo, la inserción es O (lg (n). Supongo que la inicialización es O (n) si establece un tamaño de montón b / c, el montón necesita asignar espacio y configurar la estructura de datos. Si tiene n elementos para colocar en el montón, entonces sí, cada inserción es lg (n) y hay n elementos, por lo que obtienes n * lg (n) como se indica u

Prueba de O (n)

La prueba no es elegante, y bastante sencilla, solo probé el caso de un árbol binario completo, el resultado se puede generalizar para un árbol binario completo.