En quoi la PriorityQueue de Java diffère-t-elle d'un Min-heap?

La PriorityQueue par défaut est implémentée avec Min-Heap, c'est-à-dire que l'élément supérieur est le minimum dans le tas.

Pour implémenter un max-heap, vous pouvez créer votre propre comparateur:

import java.util.Comparator;

public class MyComparator implements Comparator<Integer>
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
}

Ainsi, vous pouvez créer un Min-heap et un max-heap de la manière suivante:

PriorityQueue minHeap=new PriorityQueue();
PriorityQueue maxHeap=new PriorityQueue(size, new MyComparator());

Pour max-heap, vous pouvez utiliser:

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());

À Partir de le PriorityQueue JavaDocs:

Une file d'attente de priorité illimitée basée sur un tas de priorité. Les éléments de la file d'attente prioritaire sont classés selon leur ordre naturel, ou par un Comparator fourni au moment de la construction de la file d'attente, en fonction du constructeur utilisé.

La priorité est censée être une propriété inhérente aux objets de la file d'attente. Les éléments sont ordonnés en fonction d'une sorte de comparaison. Pour insérer un objet avec une priorité donnée, vous définissez simplement le ou les champs de l'objet qui affectent la commande, et add() ça.

Et, comme l'a commenté @Daniel ,

Généralement, les objets Java sont nommés en fonction des fonctionnalités qu'ils fournissent, et non en fonction de la façon dont ils sont implémentés.

À Partir de http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Une file d'attente de priorité illimitée basée sur un tas de priorité. 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

Pour integer, long, float, double, caractère, booléen (c'est à dire les types de données primitifs) le naturel de la commande est l'ordre croissant, c'est pourquoi Tableau.sort (arr) {où arr est un tableau de type de données primitives} trie la valeur de arr dans l'ordre croissant. Vous pouvez modifier l'ordre naturel en utilisant un comparateur

Comparateur peut être utilisé de deux façons, soit

• L'Une des manière est de savoir comment DpGeek a montré

• Une Autre façon est d'utiliser Classe Anonyme. Par exemple

Arrays.sort(arr, new Comparator<Integer> {
     public int compare(Integer x, Integer y) {
         return y - x;
     }
 }

• Si vous avez java8, vous pouvez utiliser le lambda expression

Arrays.sort(arr, (Integer x, Integer y) -> y - x);

Cela trie le tableau arr dans l'ordre décroissant

À partir de Documents Java

File d'attente prioritaire représentée comme un tas binaire équilibré : les deux enfants de file d'attente [N] sont file d'attente [2 * N + 1] et file d'attente[2*(N + 1)]. La file d'attente prioritaire est ordonnée par comparateur , ou par les éléments ' ordre naturel .

Voici un code qui fonctionne pour maxHeap et minHeap utiliser PriorityQueue -

class HeapDemo {
    private final static int HEAP_SIZE = 10; //size of heap

    //INNER CLASS
    static class maxHeapComparator implements Comparator<Integer> {
        @Override
        public int compare (Integer x, Integer y) {
            return y-x; //reverse order
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE); 
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE, new maxHeapComparator());  

        for(int i=1; i<=HeapDemo.HEAP_SIZE; ++i){
            int data = new Random().nextInt(100) +1; //number between 0 to 100
            minHeap.add(data);
            maxHeap.add(data);
        }

        System.out.print("\nMIN Heap : ");
        Iterator<Integer> iter = minHeap.iterator();
        while(iter.hasNext()){
            System.out.print(iter.next() + " ");
        }

        System.out.print("\nMAX Heap : ");
        iter = maxHeap.iterator();
        while(iter.hasNext()) {
            System.out.print(iter.next() + " ");
        }
    }
}

L'Échantillon o/p :

MIN Heap : 20 32 37 41 53 91 41 98 47 86 
MAX Heap : 98 91 41 53 86 20 37 41 32 47