c++ - array - ¿Cómo se puede implementar std:: make_heap mientras se realizan a lo sumo comparaciones 3N?

min heap complexity

Question

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

Es decir, que una colección no ordenada 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)

The while (verdadero) + __parent == 0 no son pistas sino una suposición para el comportamiento O (N)

template<typename _RandomAccessIterator, typename _Compare>
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 parece un método de registro N:

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

Es un registro estándar bog N para mí.

  template<typename _RandomAccessIterator, typename _Distance,
       typename _Tp, typename _Compare>
    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);      
      }

Cualquier pista de por qué esto es O <= 3N será apreciada.
EDITAR:

Resultados experimentales:

Esta implementación real utiliza

• <2N comparaciones para heapifying heaps
• <1.5N para acumular montones en orden inverso.

Answer 1

@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 , 2ª edición.

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

De mis experimentos (ver 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 (n-⌈log n⌉) comparaciones.

El límite de la norma 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

Answer 2

Un montón binario sobre n elementos se puede crear en tiempo O (n) usando un algoritmo inteligente y un análisis inteligente. A continuación, voy a hablar sobre cómo funciona esto, asumiendo que tiene nodos explícitos y punteros secundarios izquierdo y derecho explícitos, pero este análisis sigue siendo perfectamente válido una vez que lo comprima en una matriz.

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

1. Haga que el nuevo nodo sea la raíz del montón, ya que sus punteros secundarios izquierdo y derecho se refieren a los dos montones máximos.

2. Si bien 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 montones máximos 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 subheaps tienen tamaño cero, entonces el algoritmo termina inmediatamente con un máximo de montón de singleton, y lo hace en O (1) tiempo. Para el paso inductivo, suponga que para algunas h, este procedimiento funciona en cualquier subhome 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 cualquiera de los subárboles (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 el subchild más grande y ejecutamos este procedimiento de forma recursiva nuevamente, utilizando la raíz antigua y los dos subárboles del niño, cada uno de los cuales es de altura h. Por la hipótesis inductiva, esto significa que el subárbol que intercambiamos es ahora un máximo de pila. Por lo tanto, el montón global es un máximo, ya que la nueva raíz es más grande que todo en el subárbol con el 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, utilizando 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 la altura de los montones secundarios se reduce en uno, el tiempo de ejecución general de este algoritmo debe ser O (h).

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

1. Toma alrededor de la mitad de los nodos y crea montones singleton. (Puede calcular explícitamente cuántos nodos se necesitarán aquí, pero es aproximadamente la mitad).
2. Empareje esos montones, luego combínelos utilizando 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 valores máximos válidos, eventualmente esto produce un conjunto máximo válido en general. Si somos inteligentes con la forma en que elegimos cuántos montones de singleton para 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 corre en O (h), y en el peor de los casos 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 la profundidad de todos los árboles que fusionamos. Aproximadamente la mitad de los montones tienen profundidad cero, luego la mitad de lo que queda tiene profundidad uno, luego la mitad de los montones tiene profundidad dos, etc. Si resumimos esto, obtenemos la suma

0 * n / 2 + 1 * n / 4 + 2 * n / 8 + ... + nk / (2 ^k ) = Σ _{k = 0} ^{⌈log n⌉} (nk / 2 ^k ) = n Σ _{k = 0} ^{⌈ registro n⌉} (k / 2 ^{k + 1} )

Esto limita el número de swaps realizados. Cada intercambio requiere a lo sumo dos comparaciones. Por lo tanto, si multiplicamos la suma anterior por dos, obtenemos la siguiente suma, cuyos límites superiores es el número de swaps realizados:

n Σ _{k = 0} ^∞ (k / 2 ^k )

La suma aquí es la suma 0/2 0 + 1/2 ¹ + 2/2 ² + 3/2 ³ + .... Este es un resumen famoso que se puede evaluar de varias maneras diferentes. Una forma de evaluar esto se da en estas diapositivas de la conferencia, diapositivas 45-47 . Termina saliendo exactamente a 2n, lo que significa que la cantidad de comparaciones que se realizan está ciertamente limitada desde arriba por 3n.

¡Espero que esto ayude!