mejor manera de crear una matriz ordenada de PriorityQueue en Java

Question

lo que pueda, por supuesto, haga lo siguiente:

 PriorityQueue<Integer> q = new PriorityQueue<Integer>(100, new Comparator<Integer>() { 
      public int compare(Integer x, Integer y) { 
       return Integer.valueOf(x).compareTo(y); 
      } 
     }); 
     ...//add some elements to q 
     int[] arr = new int[q.size()]; 
     int i = 0; 
     while (q.size() != 0) { 
      arr[i++] = q.remove(); 
     } 

Pero este enfoque vaciar la cola de la que quiero seguir. Sé que podría haber ordenado usando ese comparador (por supuesto, cuando no es tan trivial como el anterior) para obtener esta matriz, pero primero tendré que crear una matriz, luego copiar elementos de la cola a la matriz, luego ordenar la matriz .

¿Hay un mejor enfoque? ¡Gracias por tu ayuda!

Answer 1

Use una LinkedList como una colección intermedia. Su constructor agrega elementos en el orden especificado por la colección proporcionada y su método toArray(T[] arr) preserva el orden de la lista.

PriorityQueue<Integer> q = new PriorityQueue<Integer>(100, new Comparator<Integer>() { 
    public int compare(Integer x, Integer y) { 
     return Integer.valueOf(x).compareTo(y); 
    } 
}); 

/* ...elided, add items... */ 

List<Integer> integers = new LinkedList<Integer>(q); 
Integer[] orderedIntegerArray = integers.toArray(new Integer[0]); 

Answer 2

Puede usar el bucle del iterador para iterar sobre una cola.

for (Iterator<Integer> iterator = q.iterator(); iterator.hasNext();) { 
    arr[i++] = iterator.next(); 
} 

Answer 3

Como Queue extends Collection, debería poder iterarlo.

for (Entero iq: queue) arr [i ++] = iq;

Hmm, si @amit tiene razón en que PriorityQueue garantiza la iteración en orden, esto no funcionará.

Sin embargo, otra edición sigue ...

Muchos de nosotros hemos aprendido que PriorityQueue no iterar en orden. Lo cual se debe a que PriorityQueue solo ordena parcialmente los elementos, principalmente rastrea el elemento principal (el menos).

Una propuesta para conservar el PriorityQueue original es hacer una copia, y tomar/drenar de la copia. La otra es hacer una lista a partir de los contenidos (ya que usted sabe el tamaño exacto, creo que una lista de arreglos es la más adecuada) y clasificarla explícitamente.

Supongo que la lista sería más rápida. Sabemos que es O (n log (n)). Ahora, los javadocs PriorityQueue dicen que las adiciones y las eliminaciones son O (log (n)). Y las llamarías N veces, entonces, en teoría, PriorityQueue también es O (n log (n)).

Sin embargo, si utilizar un PriorityQueue fuera más rápido que un ordenamiento para este caso de uso común, iterando sobre una lista ordenada, creo que habría visto muchos artículos de "consejos de rendimiento" que dicen "Use PriorityQueue en lugar de Collections.sort(). " Que no tengo. ¿Los he echado de menos?

De todos modos, el OP podría probar ambos e informar. Sería, para mí, un descubrimiento fascinante y útil si un PriorityQueue fuera más rápido que ordenar una Lista.

Hice algunas pruebas en 1 millón de enteros al azar. El ArrayList ordenado fue aproximadamente 2 veces más rápido que el drenaje de PriorityQueue en mi antiguo escritorio de 7 años, JDK6. El código sigue.

public class StackOverflow2 { 

    ArrayList<Integer> generateRandomList(int count, int seed) { 
     ArrayList<Integer> list = new ArrayList<Integer>(count); 
     Random random = new Random(); 
     random.setSeed(seed); 
     for (int i=0; i<count; i++) 
     list.add(Integer.valueOf(random.nextInt())); 

     return list; 
    } 

    long usePriorityQueue(ArrayList<Integer> inList) { 
     long total = 0; 
     long start = System.currentTimeMillis(); 

     PriorityQueue<Integer> pq = new PriorityQueue<Integer>(inList); 
     while (!pq.isEmpty()) { 
     total += pq.remove(); // do something so HotSpot doesn't optimize this away... 
     } 

     long totaltime = System.currentTimeMillis() - start; 
     System.out.println("usePriorityQueue totaltime = " + totaltime); 
     return total; 
    } 

    long useArrayList(ArrayList<Integer> inList) { 
     long total = 0; 
     long start = System.currentTimeMillis(); 

     ArrayList<Integer> list = new ArrayList<Integer>(inList); 
     Collections.sort(list); 
     for (Integer iii : list) { 
     total += iii; // do something 
     } 

     long totaltime = System.currentTimeMillis() - start; 
     System.out.println("useArrayList totaltime = " + totaltime); 
     return total; 
    } 

    public static void main(String[] args) { 
     StackOverflow2 so2 = new StackOverflow2(); 
     ArrayList<Integer> randoms = so2.generateRandomList(1000000, 123456); 

     for (int i=0; i<10; i++) { 
     long upq = so2.usePriorityQueue(randoms); 
     long ual = so2.useArrayList(randoms); 
     } 

    } 
} 

Answer 4

Si desea código de cortocircuito, siempre puede utilizar toArray() y sort:

Integer[] arr = q.toArray(new Integer[1]); 
Arrays.sort(arr,q.comparator()); 

EDIT: Usted tendrá que enviar el mismo Comparador de ordenar() si no lo hace use natural ordering [solucionó la segunda línea en el ejemplo de código]

Answer 5

Puede usar una ArrayList y luego usar la búsqueda binaria para encontrar la posición donde se coloca el elemento. Por lo tanto, la inserción se ordena

private List<Integer> items = new ArrayList<Integer>();    

while (q.size() != 0) { 
    int index = Collections.binarySearch(items, q.remove()); 
    if (index >= 0) { 
     index++; 
    } else { 
     index = -(index + 1); 
    } 
    items.add(index, q.remove); 
} 

Answer 6

¿No puede simplemente vaciar una copia de la cola original?

PriorityQueue<Integer> temp = new PriorityQueue<Integer>(q); 
int[] arr = new int[ q.size() ]; 

int i = 0; 
while (!temp.isEmpty()) { 
    arr[ i ] = temp.remove().intValue(); 
    i++; 
} 

Justo como lo hizo, pero en una cola nueva. Creo que el costo de copiar una cola de prioridad es O(n). O debería, al menos. Vaciar la cola es O(n log n), por lo que el costo final es O(n log n), al igual que obtener una matriz y luego ordenarla.

Answer 7

De los Javadocs para PriorityQueue:

Esta clase y su iterador implementar todos los métodos opcionales de las interfaces Collection y Iterator. No se garantiza que el Iterator provisto en el método iterator() atraviese los elementos de la cola de prioridad en cualquier orden en particular. Si necesita un recorrido ordenado, considere usar Arrays.sort(pq.toArray()).

Crea la matriz, luego ordénala. Es la forma prescrita.