Algoritmos y Estructuras de Datos (VJ1215)

Para mezclar dos colas de prioridad empleando montículos binarios podemos utilizar el algoritmo que construye un monticulo binario a partir de n datos iniciales dados en tiempo O(n), estudiado en el tema 4. Basta aplicar ese algoritmo a todos los datos que tienen inicialmente las dos colas a mezclar. Si ambas son de talla n, el coste temporal en el peor caso será O(2n) = O(n).

Sería una mala solución insertar los n datos de una cola en la otra con n llamadas a la operación insertar que inserta un dato, puesto que eso tendría coste temporal O(n log n).