java - Cambiar la prioridadQueue to max priorityqueue

priority queue java implementation

Question

Tengo cola de prioridad en Java de enteros:

 PriorityQueue<Integer> pq= new PriorityQueue<Integer>();

Cuando llamo a pq.poll() obtengo el elemento mínimo.

Pregunta: ¿cómo cambiar el código para obtener el elemento máximo?

Answer 1

¿Qué tal esto?

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
queue.offer(1);
queue.offer(2);
queue.offer(3);
//...

Integer val = null;
while( (val = queue.poll()) != null) {
    System.out.println(val);
}

Collections.reverseOrder() proporciona un Comparator que ordenaría los elementos en PriorityQueue en el orden opuesto a su orden natural en este caso.

Answer 2

Acabo de ejecutar una simulación Monte-Carlo en ambos comparadores en minimag de doble pila y ambos obtuvieron el mismo resultado:

Estos son los comparadores máximos que he usado:

(A) Comparador integrado de colecciones

 PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder());

(B) Comparador personalizado

PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(new Comparator<Integer>() {
    int compare(Integer lhs, Integer rhs) {
        if (rhs > lhs) return +1;
        if (rhs < lhs) return -1;
        return 0;
    }
});

Answer 3

Aquí hay un Max-Heap de muestra en Java:

PriorityQueue<Integer> pq1= new PriorityQueue<Integer>(10, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
if (x < y) return 1;
if (x > y) return -1;
return 0;
}
});
pq1.add(5);
pq1.add(10);
pq1.add(-1);
System.out.println("Peek: "+pq1.peek());

El resultado será 10

Answer 4

Los elementos de la cola de prioridad se ordenan de acuerdo con su orden natural, o por un Comparador provisto en el tiempo de construcción de la cola.

El Comparador debe anular el método de comparación.

int compare(T o1, T o2)

El método de comparación predeterminado devuelve un número entero negativo, cero o entero positivo, ya que el primer argumento es menor, igual o mayor que el segundo.

El PriorityQueue predeterminado proporcionado por Java es Min-Heap, si desea un seguimiento de montón máximo es el código

public class Sample {
    public static void main(String[] args) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {

            public int compare(Integer lhs, Integer rhs) {
                if(lhs<rhs) return +1;
                if(lhs>rhs) return -1;
                return 0;
            }
        });
        q.add(13);
        q.add(4);q.add(14);q.add(-4);q.add(1);
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }

}

Referencia: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()

Answer 5

Puede intentar presionar elementos con el signo inverso. Ej .: Agregar a = 2 & b = 5 y luego sondear b = 5.

PriorityQueue<Integer>  pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());

Una vez que haya sondeado el jefe de la cola, invierta el signo para su uso. Esto imprimirá 5 (elemento más grande). Puede ser utilizado en implementaciones ingenuas. Definitivamente no es una solución confiable. No lo recomiendo

Answer 6

Puede proporcionar un objeto Comparator personalizado que se clasifique en el orden inverso:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() {
    public int compare(Integer lhs, Integer rhs) {
        if (lhs > rhs) return +1;
        if (lhs.equals(rhs)) return 0;
        return -1;
    }
});

Ahora, la cola de prioridad revertirá todas sus comparaciones, por lo que obtendrá el elemento máximo en lugar del elemento mínimo.

¡Espero que esto ayude!

Answer 7

Puede usar MinMaxPriorityQueue (es una parte de la biblioteca de Guava): aquí está la documentación . En lugar de poll() , debe llamar al método pollLast() .

Answer 8

Puede usar la expresión lambda desde Java 8.

El siguiente código imprimirá 10, el más grande.

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
pq.add(10);
pq.add(5);
System.out.println(pq.peek());

La función lambda tomará dos enteros como parámetros de entrada, los restará entre sí y devolverá el resultado aritmético. La función lambda implementa la interfaz funcional, Comparator<T> . (Esto se usa en lugar de una clase anónima o una implementación discreta).

Answer 9

Puedes probar algo como:

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> -1 * Integer.compare(x, y));

Lo cual funciona para cualquier otra función de comparación básica que pueda tener.

Answer 10

PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);