Desde PriorityQueue Javadoc :
Nota de implementación: esta implementación proporciona tiempo O(log(n)) para poner en cola y sacar de la cola los métodos
offer,poll,remove()yadd; tiempo lineal para los métodosremove(Object)ycontains(Object); y tiempo constante para los métodos de recuperaciónpeek,elementysize.
Entonces, mi pregunta es, ¿se mantendría la complejidad del tiempo O(log(n)) para fusionar PriorityQueue s en uno? ¿O sería O(nlog(n)) considerando la inserción? ¿Y cambiaría esto si se fusionaran más montones?
Estos PriorityQueue s representan montones.
Algo como esto:
PriortityQueue<Integer> a = new PriorityQueue<>(); ... add elements PriortityQueue<Integer> b = new PriorityQueue<>(); ... add elements PriorityQueue<Integer> merged = new PriorityQueue<>(a.size() + b.size(), a.comparator()); // Assuming a and b have the same Comparator. merged.addAll(a); merged.addAll(b);Como ha señalado, el método add de la clase PriorityQueue tiene una complejidad de tiempo O(log(N)) . Si observa la implementación concreta del método addAll de la clase PriorityQueue , verá lo siguiente:
public boolean addAll(Collection<? extends E> c) { if (c == null) throw new NullPointerException(); if (c == this) throw new IllegalArgumentException(); boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; } Entonces, para cada elemento de la colección que se pasa como parámetro, se llama al método add . Por tanto, la complejidad final será O(Mlog(N)) , donde M es el número de elementos de la colección pasados como parámetro y N es el número de elementos de la cola de prioridad.