¿Cómo se puede implementar std :: make_heap al hacer, como máximo, comparaciones 3N?

Busqué el estándar C ++ 0x y encontré el requisito de que make_heap no haga más de 3 * N comparaciones.

Es decir, heapify una colección desordenada se puede hacer en O (N)

/* @brief Construct a heap over a range using comparison functor. 

¿Por qué es esto?

La fuente no me da pistas (g ++ 4.4.3)

El tiempo (verdadero) + __parent == 0 no son pistas sino una conjetura para el comportamiento de O (N)

 template void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { const _DistanceType __len = __last - __first; _DistanceType __parent = (__len - 2) / 2; while (true) { _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), __comp); if (__parent == 0) return; __parent--; } } 

__adjust_heap se parece a un método de registro N:

 while ( __secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1); 

Es un pantano estándar log N para mí.

  template void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value, _Compare __comp) { const _Distance __topIndex = __holeIndex; _Distance __secondChild = __holeIndex; while (__secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1); if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) __secondChild--; *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); __holeIndex = __secondChild; } if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) { __secondChild = 2 * (__secondChild + 1); *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + (__secondChild - 1))); __holeIndex = __secondChild - 1; } std::__push_heap(__first, __holeIndex, __topIndex, _GLIBCXX_MOVE(__value), __comp); } 

Se apreciará cualquier pista sobre por qué esto es O <= 3N.
EDITAR:

Resultados experimentales:

Esta implementación real usa

  • <2N comparaciones para heapifying montones
  • <1.5N para heapificar montones en el orden inverso.

Se puede crear un montón binario sobre n elementos en el tiempo O (n) usando un algoritmo inteligente y un análisis inteligente. En lo que sigue, voy a hablar sobre cómo funciona esto, suponiendo que tiene nodos explícitos e indicadores secundarios explícitos para el lado izquierdo y el derecho, pero este análisis sigue siendo perfectamente válido una vez que lo comprime en una matriz.

El algoritmo funciona de la siguiente manera. Comience tomando aproximadamente la mitad de los nodos y tratándolos como singleton max-montones, ya que solo hay un elemento, el árbol que contiene solo ese elemento debe ser automáticamente un montón máximo. Ahora, toma estos árboles y combínalos entre sí. Para cada par de árboles, tome uno de los valores que aún no ha utilizado y ejecute el siguiente algoritmo:

  1. Haga que el nuevo nodo sea la raíz del montón, teniendo sus punteros secundarios izquierdo y derecho para referirse a los dos max-heaps.

  2. Mientras que este nodo tiene un hijo que es más grande que él, intercambie al niño con su hijo más grande.

Mi afirmación es que este procedimiento termina produciendo un nuevo montón máximo que contiene los elementos de los dos máximos acumulados de entrada, y lo hace en el tiempo O (h), donde h es la altura de los dos montones. La prueba es una inducción sobre la altura de los montones. Como caso base, si las subventanas tienen tamaño cero, entonces el algoritmo termina inmediatamente con un max-heap de singleton, y lo hace en O (1) tiempo. Para el paso inductivo, supongamos que para algunas h, este procedimiento funciona en cualquier subelepa de tamaño h y considere lo que sucede cuando lo ejecuta en dos montones de tamaño h + 1. Cuando agregamos una nueva raíz para unir dos subárboles de tamaño h + 1, hay tres posibilidades:

  1. La nueva raíz es más grande que las raíces de ambos subárboles. Entonces, en este caso, tenemos un nuevo max-heap, ya que la raíz es más grande que cualquiera de los nodos en cualquier subárbol (por transitividad)

  2. La nueva raíz es más grande que un niño y más pequeña que la otra. Luego intercambiamos la raíz con la subimagen más grande y ejecutamos recursivamente este procedimiento nuevamente, utilizando la raíz antigua y los dos subárboles del niño, cada uno de los cuales tiene una altura h. Por la hipótesis inductiva, esto significa que el subárbol que intercambiamos ahora es un montón máximo. Así, el montón global es un montón máximo, ya que la nueva raíz es más grande que todo en el subárbol que intercambiamos (ya que es más grande que el nodo que agregamos y ya era más grande que todo en ese subárbol) y también es más grande que todo en el otro subárbol (ya que es más grande que la raíz y la raíz era más grande que todo en el otro subárbol).

  3. La nueva raíz es más pequeña que sus dos hijos. Luego, usando una versión ligeramente modificada del análisis anterior, podemos mostrar que el árbol resultante es realmente un montón.

Además, dado que en cada paso las alturas de los montones de niños disminuyen en uno, el tiempo de ejecución general para este algoritmo debe ser O (h).


En este punto, tenemos un algoritmo simple para hacer un montón:

  1. Tome aproximadamente la mitad de los nodos y cree montones de singleton. (Puede calcular explícitamente cuántos nodos se necesitarán aquí, pero es aproximadamente la mitad).
  2. Empareja esos montones, luego combínalos mediante el uso de uno de los nodos no utilizados y el procedimiento anterior.
  3. Repita el paso 2 hasta que quede un solo montón.

Como en cada paso sabemos que los montones que tenemos hasta ahora son máximos-montones válidos, eventualmente esto produce un montón máximo general válido. Si somos astutos con la forma en que elegimos cuántos montones de singleton hacer, esto también terminará creando un árbol binario completo.

Sin embargo, parece que esto debería ejecutarse en O (n lg n) tiempo, ya que hacemos O (n) fusiones, cada una de las cuales se ejecuta en O (h), y en el peor caso, la altura de los árboles que estamos fusionando es O (lg n). Pero este límite no es estricto y podemos hacerlo mucho mejor al ser más precisos con el análisis.

En particular, pensemos en qué profundidad se fusionan todos los árboles. Aproximadamente la mitad de los montones tienen profundidad cero, luego la mitad de lo que queda tiene profundidad uno, luego la mitad de lo que queda tiene profundidad dos, etc. Si summos esto, obtenemos la sum

0 * n / 2 + 1 * n / 4 + 2 * n / 8 + … + nk / (2 k ) = Σ k = 0 ⌈log n⌉ (nk / 2 k ) = n Σ k = 0 ⌈ log n⌉ (k / 2 k + 1 )

Esta parte superior limita el número de intercambios realizados. Cada intercambio requiere como máximo dos comparaciones. Por lo tanto, si multiplicamos la sum anterior por dos, obtenemos la siguiente sum, que limita el número de intercambios realizados:

n Σ k = 0 (k / 2 k )

La sum aquí es la sumtoria 0/2 0 + 1/2 1 + 2/2 2 + 3/2 3 + …. Esta es una sum famosa que se puede evaluar de múltiples maneras diferentes. Una forma de evaluar esto se da en estas diapositivas de conferencias, diapositivas 45-47 . Acaba saliendo exactamente a 2n, lo que significa que el número de comparaciones que terminan obteniéndose está ciertamente limitado desde arriba por 3n.

¡Espero que esto ayude!

@templatetypedef ya ha dado una buena respuesta de por qué el tiempo de ejecución asintótico de build_heap es O (n) . También hay una prueba en el capítulo 6 de CLRS , 2da edición.

En cuanto a por qué el estándar C ++ requiere que se utilicen como máximo 3n comparaciones:

De mis experimentos (ver el código a continuación), parece que en realidad se necesitan menos de 2n comparaciones. De hecho, estas notas de clase contienen una prueba de que build_heap solo usa 2 comparaciones (n-⌈log n⌉) .

El límite del estándar parece ser más generoso de lo requerido.


 def parent(i): return i/2 def left(i): return 2*i def right(i): return 2*i+1 def heapify_cost(n, i): most = 0 if left(i) <= n: most = 1 + heapify_cost(n, left(i)) if right(i) <= n: most = 1 + max(most, heapify_cost(n, right(i))) return most def build_heap_cost(n): return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1)) 

Algunos resultados:

 n 10 20 50 100 1000 10000 build_heap_cost(n) 9 26 83 180 1967 19960