Curso 2024/2025
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).