Algoritmo para unir dos montones máximos?

Question

¿Existe un algoritmo eficiente para combinar 2 max-heaps que se almacenan como matrices?

Answer 1

Depende de qué tipo es el montón.

Si se trata de un montón estándar donde cada nodo tiene hasta dos hijos y que se llena de que las hojas están en un máximo de dos filas diferentes, no se puede obtener más que O (n) para fusionar.

Simplemente junte las dos matrices y cree una nueva pila de ellas que tome O (n).

Para un mejor rendimiento de fusión, puede usar otra variante de pila como un Fibonacci-Heap que se puede combinar en O (1) amortizado.

Actualización: en cuenta que es peor para insertar todos los elementos de la primera pila por uno para el segundo montón o viceversa desde una inserción toma O (log (n)). A medida que sus estados de comentario, no parece saber cómo el montón se construye de manera óptima en el principio (de nuevo por una pila binaria estándar)

1. Crear una matriz y pone en los elementos de los dos montones de alguna arbitraria orden
2. ahora comienza en el nivel más bajo. El nivel más bajo contiene cantidades mínimas triviales de tamaño 1, por lo que este nivel se hace
3. sube de nivel. Cuando se viola la condición de montón de uno de los "sub-montículos", intercambie la raíz del "sub-montón" con su hijo más grande. Luego, el nivel 2 se realiza
4. pasa al nivel 3. Cuando la condición de pila se viola, proceda como antes. Intercambie con su hijo más grande y procese recursivamente hasta que todo coincida con el nivel 3
5. ...
6. cuando llegue a la cima, ha creado un nuevo montón en O (n).

Omito una prueba aquí pero puede explicarlo ya que ha hecho la mayor parte del montón en los niveles inferiores donde no tuvo que intercambiar mucho contenido para restablecer la condición de montón. Ha operado en "sub montones" mucho más pequeños, que es mucho mejor de lo que haría si insertara cada elemento en uno de los montones => luego, continuaría siempre en todo el montón que toma O (n) cada vez .

Actualización 2: Un montón binomial permite la fusión en O (log (n)) y se ajustará a su requisito O (log (n)^2).

Answer 2

Dos pilas binarias de tamaños nyk se pueden combinar en las comparaciones O (log n * log k). Veo

Jörg-R. Sack and Thomas Strothotte, An algorithm for merging heaps, Acta Informatica 22 (1985), 172-186.

Answer 3

Creo que lo que está buscando en este caso es un montón binomial.

Un montón binomial es una colección de árboles binomiales, un miembro de la familia de montón fusible. El peor tiempo de ejecución de una unión (fusión) en más de 2 binomios con n ítems totales en los montones es O (lg n).

Consulte http://en.wikipedia.org/wiki/Binomial_heap para obtener más información.