Bagaimana cara saya menggunakan PriorityQueue?

Bagaimana cara saya PriorityQueuememilah apa yang saya inginkan?

Juga, apakah ada perbedaan antara metode offerdan addmetode?

Gunakan overload konstruktor yang membutuhkan Comparator<? super E> comparatordan lulus dalam pembanding yang membandingkan dengan cara yang sesuai untuk pesanan sortir Anda. Jika Anda memberikan contoh bagaimana Anda ingin menyortir, kami dapat memberikan beberapa kode sampel untuk mengimplementasikan komparator jika Anda tidak yakin. (Ini cukup mudah.)

Seperti yang telah dikatakan di tempat lain: offerdan addhanya implementasi metode antarmuka yang berbeda. Di sumber JDK yang saya dapat, addpanggilan offer. Meskipun adddan offermemiliki perilaku yang berpotensi berbeda secara umum karena kemampuan untuk offermenunjukkan bahwa nilai tidak dapat ditambahkan karena batasan ukuran, perbedaan ini tidak relevan di PriorityQueuemana tidak terikat.

Berikut adalah contoh penyortiran antrian berdasarkan panjang string:

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

Berikut hasilnya:

pendek

medium

memang sangat lama

Solusi Java 8

Kita dapat menggunakan lambda expressionatau method referencememperkenalkan di Java 8. Jika kita memiliki beberapa nilai String yang disimpan dalam Antrian Prioritas (memiliki kapasitas 5) kami dapat menyediakan komparator sebaris (berdasarkan panjang String):

Menggunakan ekspresi lambda

PriorityQueue<String> pq=
                    new PriorityQueue<String>(5,(a,b) -> a.length() - b.length());

Menggunakan referensi Metode

PriorityQueue<String> pq=
                new PriorityQueue<String>(5, Comparator.comparing(String::length));

Maka kita dapat menggunakan salah satu dari mereka sebagai:

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

Ini akan mencetak:

Apple
PineApple
Custard Apple

Untuk membalikkan urutan (untuk mengubahnya ke antrian prioritas maksimum) cukup ubah urutan dalam pembanding inline atau gunakan reversedsebagai:

PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                             Comparator.comparing(String::length).reversed());

Kita juga bisa menggunakan Collections.reverseOrder:

PriorityQueue<Integer> pqInt = new PriorityQueue<>(10, Collections.reverseOrder());
PriorityQueue<String> pq = new PriorityQueue<String>(5, 
                Collections.reverseOrder(Comparator.comparing(String::length))

Jadi kita dapat melihat bahwa Collections.reverseOrderkelebihan beban mengambil pembanding yang dapat berguna untuk objek kustom. The reversedsebenarnya menggunakan Collections.reverseOrder:

default Comparator<T> reversed() {
    return Collections.reverseOrder(this);
}

offer () vs add ()

Sesuai dok

Metode penawaran memasukkan elemen jika memungkinkan, jika tidak, akan menghasilkan false. Ini berbeda dari metode Collection.add, yang bisa gagal menambahkan elemen hanya dengan melemparkan pengecualian yang tidak dicentang. Metode penawaran dirancang untuk digunakan ketika kegagalan adalah normal, bukan kejadian luar biasa, misalnya, dalam antrian berkapasitas tetap (atau "terikat").

Saat menggunakan antrian terbatas kapasitas, penawaran () biasanya lebih disukai untuk ditambahkan (), yang bisa gagal memasukkan elemen hanya dengan melemparkan pengecualian. Dan PriorityQueue adalah antrian prioritas tanpa batas berdasarkan tumpukan prioritas.

Cukup berikan Comparatorkepada konstruktor :

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

Satu-satunya perbedaan antara offerdan addadalah antarmuka mereka. offermilik Queue<E>, sedangkan pada addawalnya terlihat di Collection<E>antarmuka. Selain kedua metode melakukan hal yang persis sama - masukkan elemen yang ditentukan ke dalam antrian prioritas.

dari Antrian API :

Metode penawaran memasukkan elemen jika memungkinkan, jika tidak, akan menghasilkan false. Ini berbeda dari metode Collection.add, yang bisa gagal menambahkan elemen hanya dengan melemparkan pengecualian yang tidak dicentang. Metode penawaran dirancang untuk digunakan ketika kegagalan adalah hal yang normal, bukan kejadian luar biasa, misalnya, dalam antrian berkapasitas tetap (atau "terikat").

tidak berbeda, seperti yang dinyatakan dalam javadoc:

public boolean add(E e) {
    return offer(e);
}

Hanya untuk menjawab pertanyaan add()vs offer()(karena yang lain menjawab dengan sempurna imo, dan ini mungkin tidak):

Menurut JavaDoc pada antarmuka Antrian , "Metode penawaran menyisipkan elemen jika mungkin, jika tidak mengembalikan false. Ini berbeda dari metode Collection.add, yang dapat gagal menambahkan elemen hanya dengan melemparkan pengecualian yang tidak dicentang. Metode penawaran dirancang untuk gunakan ketika kegagalan adalah normal, daripada kejadian luar biasa, misalnya, dalam antrian berkapasitas tetap (atau "terikat"). "

Itu berarti jika Anda dapat menambahkan elemen (yang harus selalu menjadi kasus dalam PriorityQueue), mereka bekerja persis sama. Tetapi jika Anda tidak dapat menambahkan elemen, offer()akan memberi Anda pengembalian yang bagus dan cantik false, sambil add()melempar pengecualian yang tidak diperiksa dan tidak dicentang yang tidak Anda inginkan dalam kode Anda. Jika kegagalan untuk menambah berarti kode berfungsi sebagaimana dimaksud dan / atau itu adalah sesuatu yang akan Anda periksa secara normal, gunakan offer(). Jika kegagalan untuk menambahkan berarti ada sesuatu yang rusak, gunakan add()dan tangani pengecualian yang dihasilkan yang dilemparkan sesuai dengan spesifikasi antarmuka Collection .

Keduanya diimplementasikan dengan cara ini untuk memenuhi kontrak pada antarmuka Antrian yang menentukan offer()gagal dengan mengembalikan false( metode yang disukai dalam antrian kapasitas terbatas ) dan juga mempertahankan kontrak pada antarmuka Koleksi yang menentukan add()selalu gagal dengan melemparkan pengecualian .

Pokoknya, harapan yang menjelaskan setidaknya bagian dari pertanyaan itu.

Di sini, Kami dapat mendefinisikan komparator yang ditentukan pengguna:

Kode di bawah ini:

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

Keluaran:

   india                                               
   pakistan                                         
   bangladesh

Perbedaan antara metode menawarkan dan menambahkan: tautan

Lulus a Comparator. Isi jenis yang Anda inginkan di tempatT

Menggunakan lambdas (Java 8+):

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, (e1, e2) -> { return e1.compareTo(e2); });

Cara klasik, menggunakan kelas anonim:

int initialCapacity = 10;
PriorityQueue<T> pq = new PriorityQueue<>(initialCapacity, new Comparator<T> () {

    @Override
    public int compare(T e1, T e2) {
        return e1.compareTo(e2);
    }

});

Untuk mengurutkan dalam urutan terbalik, cukup tukar e1, e2.

Saya juga bertanya-tanya tentang pesanan cetak. Pertimbangkan kasus ini, misalnya:

Untuk antrian prioritas:

PriorityQueue<String> pq3 = new PriorityQueue<String>();

Kode ini:

pq3.offer("a");
pq3.offer("A");

dapat mencetak berbeda dari:

String[] sa = {"a", "A"}; 
for(String s : sa)   
   pq3.offer(s);

Saya menemukan jawaban dari diskusi di forum lain , di mana pengguna berkata, "metode tawaran () / tambahkan () hanya memasukkan elemen ke dalam antrian. Jika Anda ingin pesanan yang dapat diprediksi, Anda harus menggunakan mengintip / polling yang mengembalikan kepala. dari antrian. "

Sebagai alternatif untuk menggunakan Comparator, Anda juga dapat memiliki kelas yang Anda gunakan dalam PriorityQueue implementComparable Anda (dan dengan demikian menimpa compareTometode tersebut).

Perhatikan bahwa umumnya hanya baik digunakan Comparablealih-alih Comparatorjika urutan itu adalah urutan intuitif objek - jika, misalnya, Anda memiliki kasus penggunaan untuk mengurutkan Personobjek berdasarkan usia, mungkin yang terbaik adalah hanya menggunakan Comparatorsaja.

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

Keluaran:

1, short
1, medium
1, very long indeed
2, short
2, medium
2, very long indeed

Antrian Prioritas memiliki beberapa prioritas yang ditetapkan untuk setiap elemen, Elemen dengan prioritas tertinggi muncul di Top Of Queue. Sekarang, itu tergantung pada Anda bagaimana Anda ingin prioritas ditetapkan untuk masing-masing elemen. Jika tidak, Java akan melakukannya dengan cara default. Elemen dengan nilai paling rendah diberikan prioritas tertinggi dan dengan demikian dihapus dari antrian terlebih dahulu. Jika ada beberapa elemen dengan prioritas tertinggi yang sama, maka ikatnya putus secara sewenang-wenang. Anda juga dapat menentukan pemesanan menggunakan Pembanding di konstruktor PriorityQueue(initialCapacity, comparator)

Kode Contoh:

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

Keluaran:

Priority queue using Comparable:
Georgia Indiana Oklahoma Texas 
Priority queue using Comparator:
Texas Oklahoma Indiana Georgia 

Selain itu, Anda juga dapat menentukan Pembanding Kustom:

import java.util.Comparator;

public class StringLengthComparator implements Comparator<String>
{
    @Override
    public int compare(String x, String y)
    {
        //Your Own Logic
    }
}

Berikut adalah contoh sederhana yang dapat Anda gunakan untuk pembelajaran awal:

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

}