Jak uzyskać PriorityQueue
sortowanie według tego, na czym chcę sortować?
Jak uzyskać PriorityQueue
sortowanie według tego, na czym chcę sortować?
Odpowiedzi:
Użyj przeciążenia konstruktora, które pobiera Comparator<? super E> comparator
i przekazuje komparator, który porównuje w odpowiedni sposób dla twojej kolejności sortowania. Jeśli podasz przykładowy sposób sortowania, możemy podać przykładowy kod do implementacji komparatora, jeśli nie jesteś pewien. (Jest to jednak dość proste.)
Jak już zostało powiedziane w innym miejscu: offer
i add
są po prostu różne implementacje metody interfejsu. W źródle JDK, które mam, add
połączenia offer
. Chociaż add
i ogólnie offer
mają potencjalnie różne zachowanie ze względu na możliwość offer
wskazania, że wartości nie można dodać z powodu ograniczeń wielkości, różnica ta nie ma znaczenia, dla PriorityQueue
której nie ma ograniczeń.
Oto przykład sortowania kolejki priorytetowej według długości łańcucha:
// Test.java
import java.util.Comparator;
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args) {
Comparator<String> comparator = new StringLengthComparator();
PriorityQueue<String> queue = new PriorityQueue<String>(10, comparator);
queue.add("short");
queue.add("very long indeed");
queue.add("medium");
while (queue.size() != 0) {
System.out.println(queue.remove());
}
}
}
// StringLengthComparator.java
import java.util.Comparator;
public class StringLengthComparator implements Comparator<String> {
@Override
public int compare(String x, String y) {
// Assume neither string is null. Real code should
// probably be more robust
// You could also just return x.length() - y.length(),
// which would be more efficient.
if (x.length() < y.length()) {
return -1;
}
if (x.length() > y.length()) {
return 1;
}
return 0;
}
}
Oto wynik:
krótki
średni
naprawdę bardzo długo
compare
wdrożenie nie powinno być po prostu return x.length() - y.length()
? (Unikanie przewidywania gałęzi)
add()
operacji dodawania, to remove()
jest sensowne; gdybym używał offer()
, prawdopodobnie użyłbym poll()
... ale to tylko osobiste preferencje.
Możemy używać lambda expression
lub method reference
wprowadzać w Javie 8. W przypadku, gdy mamy pewne wartości String zapisane w kolejce priorytetowej (o pojemności 5), możemy zapewnić wbudowany komparator (na podstawie długości String):
Korzystanie z wyrażenia lambda
PriorityQueue<String> pq=
new PriorityQueue<String>(5,(a,b) -> a.length() - b.length());
Za pomocą odwołania do metody
PriorityQueue<String> pq=
new PriorityQueue<String>(5, Comparator.comparing(String::length));
Następnie możemy użyć dowolnego z nich jako:
public static void main(String[] args) {
PriorityQueue<String> pq=
new PriorityQueue<String>(5, (a,b) -> a.length() - b.length());
// or pq = new PriorityQueue<String>(5, Comparator.comparing(String::length));
pq.add("Apple");
pq.add("PineApple");
pq.add("Custard Apple");
while (pq.size() != 0)
{
System.out.println(pq.remove());
}
}
Spowoduje to wydrukowanie:
Apple
PineApple
Custard Apple
Aby odwrócić kolejność (aby zmienić na kolejkę o najwyższym priorytecie), wystarczy zmienić kolejność w komparatorze wbudowanym lub użyć reversed
jako:
PriorityQueue<String> pq = new PriorityQueue<String>(5,
Comparator.comparing(String::length).reversed());
Możemy również użyć Collections.reverseOrder
:
PriorityQueue<Integer> pqInt = new PriorityQueue<>(10, Collections.reverseOrder());
PriorityQueue<String> pq = new PriorityQueue<String>(5,
Collections.reverseOrder(Comparator.comparing(String::length))
Widzimy więc, że Collections.reverseOrder
jest przeciążony, aby wziąć komparator, który może być przydatny dla obiektów niestandardowych. Te reversed
rzeczywiście wykorzystuje Collections.reverseOrder
:
default Comparator<T> reversed() {
return Collections.reverseOrder(this);
}
Zgodnie z dok
Metoda oferty wstawia element, jeśli to możliwe, w przeciwnym razie zwraca false. Różni się to od metody Collection.add, która może nie dodać elementu tylko przez zgłoszenie niesprawdzonego wyjątku. Metoda oferty jest przeznaczona do użycia, gdy awaria jest zjawiskiem normalnym, a nie wyjątkowym, na przykład w kolejkach o stałej pojemności (lub „ograniczonej”).
W przypadku korzystania z kolejki o ograniczonej pojemności opcja () jest na ogół lepsza niż metoda add (), która może nie wstawić elementu tylko przez zgłoszenie wyjątku. A PriorityQueue to nieograniczona kolejka priorytetowa oparta na stercie priorytetów.
5
wskazuje początkową pojemność kolejki?
Wystarczy zaliczyć odpowiednie Comparator
do konstruktora :
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
Jedyną różnicą między offer
i add
jest interfejs, do którego należą. offer
należy do Queue<E>
, podczas gdy add
pierwotnie jest widoczny w Collection<E>
interfejsie. Poza tym obie metody robią dokładnie to samo - wstawiają określony element do kolejki priorytetowej.
Metoda oferty wstawia element, jeśli to możliwe, w przeciwnym razie zwraca false. Różni się to od metody Collection.add, która może nie dodać elementu tylko przez zgłoszenie niesprawdzonego wyjątku. Metoda oferty jest przeznaczona do użycia, gdy awaria jest zjawiskiem normalnym, a nie wyjątkowym, na przykład w kolejkach o stałej pojemności (lub „ograniczonej”).
Wystarczy odpowiedzieć na pytanie add()
vs offer()
(ponieważ na drugie pytanie jest doskonale udzielone imo, a może nie być):
Według JavaDoc w interfejsie kolejki : „Metoda oferty wstawia element, jeśli to możliwe, w przeciwnym razie zwraca false. Różni się to od metody Collection.add, która może nie dodać elementu tylko przez zgłoszenie niesprawdzonego wyjątku. Metoda oferty jest przeznaczona dla używaj, gdy awaria jest zjawiskiem normalnym, a nie wyjątkowym, na przykład w kolejkach o stałej pojemności (lub „ograniczonej”). ”
Oznacza to, że jeśli możesz dodać element (co powinno zawsze mieć miejsce w przypadku PriorityQueue), działają one dokładnie tak samo. Ale jeśli nie możesz dodać elementu, offer()
da ci ładny i ładny false
zwrot, a add()
zgłasza nieprzyjemny wyjątek, którego nie chcesz w swoim kodzie. Jeśli brak dodania oznacza, że kod działa zgodnie z przeznaczeniem i / lub sprawdzasz go normalnie, użyj offer()
. Jeśli brak dodawania oznacza, że coś jest zepsute, użyj add()
i obsłuż wynikowy wyjątek zgłoszony zgodnie ze specyfikacjami interfejsu kolekcji .
Oba są zaimplementowane w ten sposób, aby wypełnić kontrakt na interfejsie kolejki, który określa offer()
awarie poprzez zwrócenie false
( metoda preferowana w kolejkach o ograniczonej pojemności ), a także utrzymać kontrakt na interfejsie kolekcji, który określa,add()
że zawsze kończy się niepowodzeniem przez zgłoszenie wyjątku .
W każdym razie, mam nadzieję, że wyjaśni to przynajmniej tę część pytania.
Tutaj możemy zdefiniować komparator zdefiniowany przez użytkownika:
Poniżej kodu:
import java.util.*;
import java.util.Collections;
import java.util.Comparator;
class Checker implements Comparator<String>
{
public int compare(String str1, String str2)
{
if (str1.length() < str2.length()) return -1;
else return 1;
}
}
class Main
{
public static void main(String args[])
{
PriorityQueue<String> queue=new PriorityQueue<String>(5, new Checker());
queue.add("india");
queue.add("bangladesh");
queue.add("pakistan");
while (queue.size() != 0)
{
System.out.printf("%s\n",queue.remove());
}
}
}
Wynik :
india pakistan bangladesh
Różnica między ofertą a metodami dodawania: link
Podaj to Comparator
. Wpisz żądany typ zamiastT
Korzystanie z lambdas (Java 8+):
int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });
Klasyczny sposób, z wykorzystaniem anonimowej klasy:
int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {
@Override
public int compare(T e1, T e2) {
return e1.compareTo(e2);
}
});
Aby posortować w odwrotnej kolejności, po prostu zamień e1, e2.
Zastanawiałem się także nad kolejnością drukowania. Rozważ ten przypadek, na przykład:
W przypadku kolejki priorytetowej:
PriorityQueue<String> pq3 = new PriorityQueue<String>();
Ten kod:
pq3.offer("a");
pq3.offer("A");
może drukować inaczej niż:
String[] sa = {"a", "A"};
for(String s : sa)
pq3.offer(s);
Znalazłem odpowiedź z dyskusji na innym forum , na której użytkownik powiedział: „metody offer () / add () wstawiają tylko element do kolejki. Jeśli chcesz przewidzieć kolejność, powinieneś użyć peek / poll, które zwracają głowę w kolejce. ”
Alternatywą dla użycia Comparator
może być także klasa, której używasz w swoim PriorityQueue
narzędziuComparable
(i odpowiednio przesłonić compareTo
metodę).
Zauważ, że generalnie najlepiej jest używać Comparable
zamiast tego, Comparator
jeśli porządkowanie jest intuicyjne porządkowanie obiektu - jeśli na przykład masz przypadek użycia do sortowania Person
obiektów według wieku, prawdopodobnie najlepiej po prostu użyć Comparator
zamiast tego.
import java.lang.Comparable;
import java.util.PriorityQueue;
class Test
{
public static void main(String[] args)
{
PriorityQueue<MyClass> queue = new PriorityQueue<MyClass>();
queue.add(new MyClass(2, "short"));
queue.add(new MyClass(2, "very long indeed"));
queue.add(new MyClass(1, "medium"));
queue.add(new MyClass(1, "very long indeed"));
queue.add(new MyClass(2, "medium"));
queue.add(new MyClass(1, "short"));
while (queue.size() != 0)
System.out.println(queue.remove());
}
}
class MyClass implements Comparable<MyClass>
{
int sortFirst;
String sortByLength;
public MyClass(int sortFirst, String sortByLength)
{
this.sortFirst = sortFirst;
this.sortByLength = sortByLength;
}
@Override
public int compareTo(MyClass other)
{
if (sortFirst != other.sortFirst)
return Integer.compare(sortFirst, other.sortFirst);
else
return Integer.compare(sortByLength.length(), other.sortByLength.length());
}
public String toString()
{
return sortFirst + ", " + sortByLength;
}
}
Wynik:
1, short
1, medium
1, very long indeed
2, short
2, medium
2, very long indeed
Kolejka priorytetowa ma pewien priorytet przypisany do każdego elementu. Element o najwyższym priorytecie pojawia się na początku kolejki. Teraz zależy od Ciebie, w jaki sposób chcesz przypisać priorytet każdemu z elementów. Jeśli tego nie zrobisz, Java zrobi to domyślnie. Element o najmniejszej wartości ma najwyższy priorytet i dlatego jest najpierw usuwany z kolejki. Jeśli jest kilka elementów o tym samym najwyższym priorytecie, remis zostaje zerwany arbitralnie. Możesz także określić kolejność za pomocą Komparatora w konstruktorze PriorityQueue(initialCapacity, comparator)
Przykładowy kod:
PriorityQueue<String> queue1 = new PriorityQueue<>();
queue1.offer("Oklahoma");
queue1.offer("Indiana");
queue1.offer("Georgia");
queue1.offer("Texas");
System.out.println("Priority queue using Comparable:");
while (queue1.size() > 0) {
System.out.print(queue1.remove() + " ");
}
PriorityQueue<String> queue2 = new PriorityQueue(4, Collections.reverseOrder());
queue2.offer("Oklahoma");
queue2.offer("Indiana");
queue2.offer("Georgia");
queue2.offer("Texas");
System.out.println("\nPriority queue using Comparator:");
while (queue2.size() > 0) {
System.out.print(queue2.remove() + " ");
}
Wynik:
Priority queue using Comparable:
Georgia Indiana Oklahoma Texas
Priority queue using Comparator:
Texas Oklahoma Indiana Georgia
W przeciwnym razie możesz także zdefiniować własny komparator:
import java.util.Comparator;
public class StringLengthComparator implements Comparator<String>
{
@Override
public int compare(String x, String y)
{
//Your Own Logic
}
}
Oto prosty przykład, którego możesz użyć do wstępnej nauki:
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
public class PQExample {
public static void main(String[] args) {
//PriorityQueue with Comparator
Queue<Customer> cpq = new PriorityQueue<>(7, idComp);
addToQueue(cpq);
pollFromQueue(cpq);
}
public static Comparator<Customer> idComp = new Comparator<Customer>(){
@Override
public int compare(Customer o1, Customer o2) {
return (int) (o1.getId() - o2.getId());
}
};
//utility method to add random data to Queue
private static void addToQueue(Queue<Customer> cq){
Random rand = new Random();
for(int i=0;i<7;i++){
int id = rand.nextInt(100);
cq.add(new Customer(id, "KV"+id));
}
}
private static void pollFromQueue(Queue<Customer> cq){
while(true){
Customer c = cq.poll();
if(c == null) break;
System.out.println("Customer Polled : "+c.getId() + " "+ c.getName());
}
}
}