Hoe verschilt Java’s PriorityQueue van een min-heap?

Waarom hebben ze PriorityQueuegenoemd als je niet kunt insertWithPriority? Het lijkt erg op een hoop. Zijn er verschillen? Als er geen verschil is, waarom heette het dan PriorityQueueen niet Heap?


Antwoord 1, autoriteit 100%

Add() werkt als een insertWithPriority.

U kunt prioriteit definiëren voor het type dat u wilt met behulp van de constructor:

PriorityQueue(int, java.util.Comparator)

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

De volgorde die de vergelijker geeft, vertegenwoordigt de prioriteit in de wachtrij.


Antwoord 2, autoriteit 96%

De standaard PriorityQueue is geïmplementeerd met Min-Heap, dat wil zeggen dat het bovenste element het minimum in de heap is.

Om een ​​max-heap te implementeren, kunt u uw eigen vergelijker maken:

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

Je kunt dus op de volgende manier een min-heap en max-heap maken:

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

Antwoord 3, autoriteit 90%

Voor max-heap kun je gebruiken:

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

Antwoord 4, autoriteit 19%

Van de PriorityQueueJavaDocs:

Een onbegrensde prioriteitswachtrij op basis van een prioriteitshoop. De elementen van de prioriteitswachtrij worden geordend volgens hun natuurlijke volgorde, of door een Comparatordie tijdens de bouwtijd van de wachtrij wordt verstrekt, afhankelijk van welke constructor wordt gebruikt.

Prioriteit is bedoeld als een inherente eigenschap van de objecten in de wachtrij. De elementen zijn geordend op basis van een soort vergelijking. Om een ​​object met een bepaalde prioriteit in te voegen, stelt u de velden van het object in die de volgorde beïnvloeden, en add()het.


En, zoals @Danielopmerkte,

Over het algemeen krijgen Java-objecten een naam op basis van de functionaliteit die ze bieden, niet op basis van hoe ze zijn geïmplementeerd.


Antwoord 5, autoriteit 12%

Van Java-documenten

Prioriteitswachtrij weergegeven als een gebalanceerde binaire hoop: de twee kinderen van wachtrij[n] zijn wachtrij[2*n+1] en wachtrij[2*(n+1)]. De prioriteitswachtrij is geordend op comparator, of op de natuurlijke volgordevan de elementen.


Hier is een werkende code voor maxHeapen minHeapmet behulp van 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() + " ");
        }
    }
}

voorbeeld 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 

Antwoord 6, autoriteit 6%

Van http://docs.oracle. com/javase/7/docs/api/java/util/PriorityQueue.html

Een onbegrensde prioriteitswachtrij op basis van een prioriteitshoop. De elementen van de prioriteitswachtrij worden geordend volgens hun natuurlijke volgorde, of door een Comparatordie wordt verstrekt tijdens de bouwtijd van de wachtrij

voor integer, long, float, double, character, boolean (dwz primitieve gegevenstypen) is de natuurlijke volgordeoplopende volgorde, daarom is Arrays.sort(arr) {waar arr een array is van primitief gegevenstype} sorteert de waarde van arr in oplopende volgorde. U kunt de natuurlijke volgorde wijzigen met behulp van een Comparator

Vergelijker kan op twee manieren worden gebruikt

  • Een van de manieren is hoe DpGeekliet zien

  • Een andere manier is door gebruik te maken van Anonieme klasse. Bijvoorbeeld

Arrays.sort(arr, new Comparator<Integer>() {
     public int compare(Integer x, Integer y) {
         return y - x;
     }
});
  • Als je java8 hebt, kun je de lambda-expressie gebruiken

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

Dit sorteert de array arr in aflopende volgorde

LEAVE A REPLY

Please enter your comment!
Please enter your name here

15 − 8 =

Other episodes