ordenar - ejercicios de colas de prioridad java

Convirtiendo una PriorityQue de Java en una cola de prioridad estable

Question

Estoy intentando implementar una cola de prioridad estable (primero en entrar, primero en salir) en Java. Suponiendo que la clave es un nombre y el valor es una edad, sé que puedo hacer una cola de prioridad inestable como esta:

Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(100, ageComparator);

Esto hace prácticamente todo lo que necesito, excepto que no mantiene el orden de los pares clave-valor cuando los inserto (o los elimino).

Encontré una solución alternativa al crear una LinkedList, que ofrece esencialmente la misma funcionalidad, excepto que no incluye un constructor con una opción de comparación, y creo que debe ser más lenta ya que mantengo el orden de los valores. llamando a Collections.sort() después de cada operación de cola.

Así que supongo que realmente hay dos opciones que me interesan. Primero, ¿cómo podría editar el PriorityQueue anterior para mantener el orden de inserción y eliminación? O, en segundo lugar, ¿cómo podría forzar a mi opción LinkedList a usar un comparador de forma inmediata en lugar de tener que ordenar una clasificación en cada operación? ¡Gracias!

EDITAR:

Gracias por la buena pregunta en el primer comentario que se publicó. Por FIFO, quiero decir que para los pares clave-valor con valores iguales, primero se debe extraer el par que se coloca primero.

Answer 1

Keap-based PriorityQueue es naturalmente estable. Está escrito en Kotlin, por lo que puede reemplazar java.util.PriorityQueue en código Java.

Answer 2

Necesitas algo como esto:

import java.util.AbstractMap;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.concurrent.atomic.AtomicInteger;

public class PriorityTest {
  @SuppressWarnings("serial")
  private static class Entry extends AbstractMap.SimpleEntry<String, Integer> {
    private final static AtomicInteger seq = new AtomicInteger(0);
    final int order;
    public Entry(final String _key, final Integer _value) {
      super(_key, _value);
      order = seq.incrementAndGet();
    }
  }

  private static class OrderedComparator implements Comparator<Entry> {
    @Override
    public int compare(final Entry _e1, final Entry _e2) {
      int r = _e1.getValue().compareTo(_e2.getValue());
      if (r == 0)
        return Integer.compare(_e1.order, _e2.order);
      return r;
    }
  }

  public static void main(String[] args) {
    final PriorityQueue<Entry> pq = new PriorityQueue<Entry>(10, new OrderedComparator());
    pq.add(new Entry("Jane", 22));
    pq.add(new Entry("John", 15));
    pq.add(new Entry("Bill", 45));
    pq.add(new Entry("Bob", 22));
    while(!pq.isEmpty()) {
      System.out.println(pq.remove());
    }
  }
}