Changer la priorité de file d'attente en priorité maximale

J'ai une file d'attente prioritaire dans Java of Integers:

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

Quand j'appelle, pq.poll()j'obtiens l'élément minimum.

Question: comment changer le code pour obtenir le maximum d'élément?

Et comme ça:

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);
}

Le Collections.reverseOrder()fournit un Comparatorqui PriorityQueuetrierait les éléments dans un ordre opposé à leur ordre naturel dans ce cas.

Vous pouvez utiliser l'expression lambda depuis Java 8.

Le code suivant imprimera 10, le plus grand.

// There is overflow problem when using simple lambda as comparator, as pointed out by Фима Гирин.
// PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

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

pq.add(10);
pq.add(5);
System.out.println(pq.peek());

La fonction lambda prendra deux entiers comme paramètres d'entrée, les soustrayera l'un de l'autre et retournera le résultat arithmétique. La fonction lambda implémente l'interface fonctionnelle, Comparator<T>. (Ceci est utilisé sur place, par opposition à une classe anonyme ou à une implémentation discrète.)

Vous pouvez fournir un Comparatorobjet personnalisé qui classe les éléments dans l'ordre inverse:

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;
    }
});

Maintenant, la file d'attente prioritaire inversera toutes ses comparaisons, vous obtiendrez donc l'élément maximum plutôt que l'élément minimum.

J'espère que cela t'aides!

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

Dans Java 8+, vous pouvez créer une file d'attente de priorité maximale via l'une de ces méthodes:

Méthode 1:

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

Méthode 2:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a); 

Méthode 3:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a)); 

Les éléments de la file d'attente prioritaire sont classés selon leur ordre naturel, ou par un comparateur fourni au moment de la construction de la file d'attente.

Le comparateur doit remplacer la méthode de comparaison.

int compare(T o1, T o2)

La méthode de comparaison par défaut renvoie un entier négatif, zéro ou un entier positif car le premier argument est inférieur, égal ou supérieur au second.

La PriorityQueue par défaut fournie par Java est Min-Heap, si vous voulez un tas max suivant est le code

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());
        }
    }

}

Référence: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator ()

Voici un exemple de Max-Heap 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());

La sortie sera 10

Ceci peut être réalisé par le code ci-dessous dans Java 8 qui a introduit un constructeur qui ne prend qu'un comparateur.

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

Vous pouvez utiliser MinMaxPriorityQueue(cela fait partie de la bibliothèque Guava): voici la documentation . Au lieu de poll(), vous devez appeler la pollLast()méthode.

Remplacez PriorityQueue par MAX PriorityQueue Méthode 1: Queue pq = new PriorityQueue <> (Collections.reverseOrder ()); Méthode 2: Queue pq1 = new PriorityQueue <> ((a, b) -> b - a); Regardons quelques exemples:

public class Example1 {
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        System.out.println("......................");
        // another way
        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        /* OUTPUT
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
          Max element in the list => 888
          ......................
           Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
           Max element in the list => 888

         */


    }
}

Prenons une interview célèbre Problème: Kth plus grand élément d'un tableau en utilisant PriorityQueue

public class KthLargestElement_1{
    public static void main(String[] args) {

        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.addAll(ints);
        System.out.println("Priority Queue => " + pq);
        System.out.println("Max element in the list => " + pq.peek());
        while (--k > 0) {
            pq.poll();
        } // while
        System.out.println("Third largest => " + pq.peek());
/*
 Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
Third largest => 666

 */
    }
}

Autrement :

public class KthLargestElement_2 {
    public static void main(String[] args) {
        List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
        int k = 3;

        Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
        pq1.addAll(ints);
        System.out.println("Priority Queue => " + pq1);
        System.out.println("Max element in the list => " + pq1.peek());
        while (--k > 0) {
            pq1.poll();
        } // while
        System.out.println("Third largest => " + pq1.peek());
        /*
          Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222] 
          Max element in the list => 888 
          Third largest => 666

         */
    }
}

Comme on peut le voir, les deux donnent le même résultat.

Ceci peut être réalisé en utilisant

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

Je viens de lancer une simulation Monte-Carlo sur les deux comparateurs sur un tri à double tas min max et ils sont tous les deux arrivés au même résultat:

Voici les comparateurs max que j'ai utilisés:

(A) Comparateur intégré de collections

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

(B) Comparateur personnalisé

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;
    }
});

Vous pouvez essayer quelque chose comme:

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

Ce qui fonctionne pour toute autre fonction de comparaison de base que vous pourriez avoir.

PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));

Vous pouvez essayer de pousser des éléments avec un signe inverse. Par exemple: pour ajouter a = 2 & b = 5 puis interroger b = 5.

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

Une fois que vous interrogez la tête de la file d'attente, inversez le signe de votre utilisation. Cela imprimera 5 (élément plus grand). Peut être utilisé dans des implémentations naïves. Ce n'est certainement pas une solution fiable. Je ne le recommande pas.

Nous pouvons le faire en créant notre classe CustomComparator qui implémente l'interface Comparator et en remplaçant sa méthode de comparaison. Voici le code pour le même:

import java.util.PriorityQueue;
import java.util.Comparator;
public class Main
{
    public static void main(String[] args) {
        PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
        nums.offer(21);
        nums.offer(1);
        nums.offer(8);
        nums.offer(2);
        nums.offer(-4);
        System.out.println(nums.peek());
    }
}
class CustomComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer n1, Integer n2){
        int val = n1.compareTo(n2);
        if(val > 0)
           return -1;
        else if(val < 0)
            return 1;
        else
            return 0;
    }
}