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

Question

Pourquoi ont-ils nommé PriorityQueue si vous ne pouvez pas insertWithPriority ? Cela semble très similaire à un tas. Y a-t-il des différences ? S'il n'y a pas de différence, alors pourquoi a-t-il été nommé PriorityQueue et pas Heap ?

Answer 1

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

Afin d'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());

Answer 2

Pour le max-heap, vous pouvez utiliser :

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

Answer 3

Add() fonctionne comme un insertWithPriority.

Vous pouvez définir la priorité pour le type que vous voulez en utilisant le constructeur :

PriorityQueue(int, java.util.Comparator)

regardez en dessous https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

L'ordre donné par le comparateur représentera la priorité dans la file d'attente.

Answer 4

Comportement par défaut tel que décrit dans les autres réponses

Min Heap (par défaut) :

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

Pour Max Heap :

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2-o1);

Answer 5

De Docs Java

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

---

Voici un code fonctionnel pour maxHeap y minHeap en utilisant 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() + " ");
        }
    }
}

é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