Antrian Prioritas Java: bukan antrean klasik

Pada artikel ini kita mempelajari antrian prioritas, kelas Java, yang mengimplementasikan antarmuka Queue. Apa yang diketahui programmer tentang Antarmuka Antrian biasa? Pertama-tama, antarmuka ini didasarkan pada prinsip FIFO atau “first in first out”. Itu mengingatkan antrian biasa dalam arti umumnya. Anda ingin mendapatkan kopi dari McDrive? Jika mobil Anda adalah yang pertama di dekat jendela, Anda akan mendapatkan kopi sebelum pengemudi berikutnya.

Deklarasi Antarmuka Antrian

public interface Queue<E> extends Collection<E>

Apa itu Antrian Prioritas

Apa itu Antrean Prioritas? Pertama-tama itu adalah kelas yang mengimplementasikan antarmuka Queue jika memasukkan elemen dari belakang dan menghapus elemen dari kepala. Namun itu bukan antrian biasa di dalam. Urutan elemen antrian prioritas Java tergantung pada prioritas elemen. Elemen dengan prioritas tertinggi akan dipindahkan ke kepala antrian. Jika Anda menghapus (melayani) elemen dengan peringkat tertinggi, yang kedua pergi ke kepala untuk mendapatkan kopinya. Bagaimana prioritas ditentukan? Menurut dokumentasi, elemen antrian prioritas diurutkan sesuai urutan alaminya, atau oleh Pembanding yang disediakan pada waktu konstruksi antrian, bergantung pada konstruktor mana yang digunakan. Antrean prioritas berdasarkan tumpukan min prioritas. Artinya, dalam hal elemen antrian angka, elemen pertama dari antrian akan menjadi minimal dari angka-angka ini. Cukup sering setelah membaca definisi ini, siswa pemula mulai berpikir bahwa antrian prioritas diurutkan secara linier. Artinya, jika, katakanlah, kita menggunakan antrian yang elemennya adalah bilangan asli, maka elemen pertama akan menjadi yang terkecil, dan yang terakhir akan menjadi yang terbesar. Ini tidak sepenuhnya benar. Untuk memahami cara kerja antrean prioritas dan apa yang diberikannya, Anda perlu mengetahui cara kerja heap. Kami mempertimbangkan struktur internal antrian prioritas menggunakan contoh nanti. Sekarang mari kita memikirkan atribut eksternalnya. maka elemen pertama akan menjadi yang terkecil, dan yang terakhir akan menjadi yang terbesar. Ini tidak sepenuhnya benar. Untuk memahami cara kerja antrean prioritas dan apa yang diberikannya, Anda perlu mengetahui cara kerja heap. Kami mempertimbangkan struktur internal antrian prioritas menggunakan contoh nanti. Sekarang mari kita memikirkan atribut eksternalnya. maka elemen pertama akan menjadi yang terkecil, dan yang terakhir akan menjadi yang terbesar. Ini tidak sepenuhnya benar. Untuk memahami cara kerja antrean prioritas dan apa yang diberikannya, Anda perlu mengetahui cara kerja heap. Kami mempertimbangkan struktur internal antrian prioritas menggunakan contoh nanti. Sekarang mari kita memikirkan atribut eksternalnya.

Deklarasi dan konstruktor kelas PriorityQueue

Kelas PriorityQueue menyediakan 6 cara berbeda untuk membuat antrian prioritas di Java.

• PriorityQueue() - antrian kosong dengan kapasitas awal default (11) yang mengurutkan elemen-elemennya sesuai dengan urutan aslinya.
• PriorityQueue(Collection c) - antrian kosong yang berisi elemen dalam koleksi yang ditentukan.
• PriorityQueue(int initialCapacity) - antrian kosong dengan kapasitas awal yang ditentukan yang mengurutkan elemennya sesuai dengan urutan aslinya.
• PriorityQueue(int initialCapacity, Comparator comparator) - antrian kosong dengan kapasitas awal yang ditentukan yang mengurutkan elemennya sesuai dengan pembanding yang ditentukan.
• PriorityQueue(PriorityQueue c) - antrian kosong yang berisi elemen dalam antrian prioritas yang ditentukan.
• PriorityQueue(SortedSet c) - antrian kosong yang berisi elemen dalam set terurut yang ditentukan.

Antrian Prioritas di Jawa dideklarasikan dengan cara berikut:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Membuat PriorityQueue

Mari buat antrian prioritas bilangan bulat. Implementasi Antrian Prioritas, kode Java:

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

Kami telah membuat antrean prioritas tanpa argumen. Dalam hal ini, kepala antrian prioritas adalah jumlah minimal antrian. Jika Anda melepas kepala, elemen terkecil berikutnya akan menempati tempat ini. Jadi, Anda dapat menghapus elemen dari antrean dalam urutan menaik. Jika perlu Anda dapat mengubah prinsip pengurutan menggunakan antarmuka Komparator.

Metode Java PriorityQueue

Kelas PriorityQueue Java memiliki metode penting untuk menambah, menghapus, dan memeriksa elemen.

Masukkan Elemen ke dalam Antrean Prioritas

• boolean add(object) menyisipkan elemen yang ditentukan ke dalam antrian prioritas. Mengembalikan true jika berhasil. Jika antrean penuh, metode melontarkan pengecualian.
• boolean offer(object) menyisipkan elemen tertentu ke dalam antrian prioritas ini. Jika antrian sudah penuh, metode mengembalikan false.

Anda dapat menggunakan kedua operasi penambahan, tidak ada perbedaan untuk sebagian besar kasus. Berikut adalah sedikit contoh inisiasi dan penambahan elemen ke dalam antrian prioritas.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

Outputnya adalah:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

Urutan elemennya sepertinya aneh, kami akan menjelaskannya nanti.

Mengambil dan menghapus elemen dari Priority Queue

• boolean remove(object) menghapus satu instance dari elemen yang ditentukan dari antrian ini, jika ada.
• Polling objek () mengambil dan menghapus kepala antrian ini. Mengembalikan null jika antrian kosong.
• void clear() menghapus semua elemen dari antrian prioritas.
• Elemen objek () mengambil kepala antrian ini tanpa menghapusnya. Melempar NoSuchElementException jika antrean kosong.
• Object peek() mengambil kepala antrian tanpa menghapusnya. Mengembalikan null jika antrian kosong.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Hasil:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Seperti yang Anda lihat, mencoba mencetak kepala Queue kosong menggunakan metode element() mengarah ke NoSuchElementexception .

Pembanding Antrean Prioritas

• Comparator comparator() mengembalikan komparator yang digunakan untuk mengurutkan elemen dalam antrian. Mengembalikan nol jika antrean diurutkan menurut urutan alami elemennya.

Antrean prioritas Java, contoh dengan pembanding

Kita menggunakan urutan natural (ascending) pada contoh kode di atas, tetapi terkadang kita harus mengubahnya. Berikut adalah contoh antrean prioritas Java, di mana kami membuat kelas pembanding internal kami sendiri yang mengimplementasikan antarmuka Pembanding. Komparator kami akan mengurutkan elemen dari yang terbesar hingga yang terkecil.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Hasil:

the head of Queue = 5
5
4
3
2
1

Head of Queue sekarang bukan elemen minimal, tapi maksimal, dan urutannya diubah menjadi terbalik.

Mengulangi PriorityQueue menggunakan iterator

ProrityQueue adalah bagian dari kerangka Koleksi dan mengimplementasikan antarmuka Iterable<> . Untuk mengulangi elemen antrean prioritas, Anda dapat menggunakan metode iterator() . Ini contohnya:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Hasil:

1 2 4 5 3 

Lebih banyak metode PriorityQueue

• boolean berisi(Objek o) mengembalikan true jika antrian berisi elemen o.
• int size() mengembalikan jumlah elemen dalam antrian ini.
• Object[] toArray() mengembalikan array yang berisi semua elemen dalam antrian ini.

Ini contohnya:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Hasil:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

Definisi PriorityQueue Java 8

Jika Anda membuka dokumentasi java 8 priorityqueue, Anda akan menemukan definisi berikutnya: Antrean prioritas tanpa batas berdasarkan tumpukan prioritas. Elemen-elemen antrian prioritas diurutkan sesuai urutan alaminya, atau oleh Pembanding yang disediakan pada waktu konstruksi antrian, bergantung pada konstruktor mana yang digunakan. Antrian prioritas tidak mengizinkan elemen nol. Antrean prioritas yang mengandalkan pengurutan alami juga tidak mengizinkan penyisipan objek yang tidak sebanding (melakukannya dapat mengakibatkan ClassCastException). Tumpukan adalah kata yang sangat penting di sini. Ini menjelaskan properti pengurutan elemen Antrean Prioritas.

Prinsip kerja PriorityQueue: Binary Heap

Mari kita mulai dengan sebuah contoh. Mari buat dua objek yang mengimplementasikan antarmuka Queue. Salah satunya LinkedList, yang kedua — PriorityQueue. Keduanya memiliki 5 elemen Integer (1,2,3,4 dan 5) dan kami mulai memasukkan elemen ke dalam antrian kami dari yang terbesar hingga yang terkecil. Jadi, yang pertama datang 5, lalu 4, 3, 2 dan yang terakhir adalah 1. Kemudian cetak kedua daftar untuk memeriksa urutannya.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Hasil dari kerja kode ini adalah sebagai berikut:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Nah, urutan linkedlist dapat diprediksi dan dimengerti. Itu dipesan sesuai dengan prinsip FIFO. Kita mulai dengan 5, jadi elemen ini adalah baris paling pertama, lalu 4 dan seterusnya. Apa yang bisa kami ceritakan tentang urutan antrean prioritas? Docs mengatakan bahwa elemen antrean prioritas diurutkan sesuai urutan alaminya, atau oleh Pembanding yang disediakan pada waktu konstruksi antrean. Namun urutan ini tampaknya tidak "alami" dalam arti penyortiran linier. Kami lebih suka mengharapkan [1, 2, 3, 4, 5], bukan [1, 2, 4, 5, 3]. Untuk memahami mengapa urutan pengambilan seperti itu, kita harus mengingat antrian prioritas berdasarkan tumpukan. Apa itu tumpukan? Ini adalah struktur data berdasarkan pohon biner. Properti utama heap: prioritas setiap orang tua lebih besar daripada prioritas anak-anaknya. Izinkan saya mengingatkan Anda bahwa sebuah pohon disebut biner lengkap jika setiap orang tua tidak memiliki lebih dari dua anak, dan pengisian level dilakukan dari atas ke bawah (dari level yang sama - dari kiri ke kanan). Tumpukan biner mengatur ulang dirinya sendiri setiap kali elemen ditambahkan atau dihapus darinya. Dalam kasus min-heap, elemen terkecil masuk ke root terlepas dari urutan penyisipannya. Antrean prioritas berdasarkan min-heap ini. Artinya, dalam kasus elemen antrian angka, elemen antrian pertama akan menjadi minimal dari angka-angka ini. Jika Anda menghapus root, terkecil berikutnya menjadi root.

Mari beralih ke contoh kita.

Langkah 1. Kami memasukkan '5' ke dalam antrian prioritas. Itu menjadi akar. Langkah 2. Kami menambahkan '4' ke dalam antrian prioritas. 4 <5, jadi elemen baru harus lebih tinggi dari elemen lama. Angka 4 menjadi akar, 5 adalah anak kirinya. Sekarang struktur data di Java adalah [4, 5] Langkah 3. Kita tambahkan '3'. Untuk sementara ia menjadi anak kanan dari akar (4). Namun, 3 < 4, jadi kita harus mengangkatnya. Tukarkan 3 dan 4. Sekarang kita memiliki struktur seperti [3, 5, 4] Langkah 4. Kita tambahkan '2'. Itu menjadi anak kiri dari 5. 2<5, jadi tukarkan. 2 menjadi anak kiri dari 3, 2 < 3, jadi satu lagi proses pertukaran. Sekarang kita memiliki struktur [2,3,4,5] Langkah 5.Kami menambahkan '1'. Itu berasal dari anak kanan dari 3 ke anak kiri dari 2, dan kemudian pergi ke root. Struktur data hasil: [1,2,4,5,3] Proses Penghapusan dimulai dari akar, dan memicu prosedur sebaliknya. Jadi, pertama kita memiliki 1 sebagai root, lalu 2, 3, 4 dan terakhir 5. Itu sebabnya menggunakan operasi menghapus poll()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

kami telah "diurutkan" dalam keluaran akal linier:

1
2
3
4
5

Jadi antrian prioritas bisa efektif untuk beberapa operasi. Butuh waktu O(log N) untuk menyisipkan dan menghapus setiap elemen, dan Anda bisa mendapatkan elemen minimal dalam O(1). Ini contoh lengkapnya:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Penting untuk dipahami bahwa antrian prioritas didasarkan pada tumpukan biner, sehingga mereka tidak menyimpan elemen dalam urutan terurut linier. Setiap jalan dari akar ke daun diurutkan, tetapi jalan yang berbeda dari akar tidak. Artinya, Anda bisa mendapatkan elemen antrean minimal dengan sangat cepat.

Apa yang harus Anda ketahui tentang antrian prioritas. Daftar singkat

• Antrean Prioritas tidak mengizinkan objek NULL.
• Anda hanya dapat menambahkan objek yang sebanding ke dalam PriorityQueue.
• Antrean prioritas dibangun sebagai min heap, sejenis pohon biner. Elemen minimal adalah root. Objek antrian prioritas diurutkan secara default dalam urutan alami.
• Anda dapat menggunakan Pembanding jika Anda membutuhkan pemesanan khusus.
• PriorityQueue tidak aman untuk thread, jadi lebih baik Anda menggunakan PriorityBlockingQueue untuk bekerja di lingkungan yang bersamaan.
• PriorityQueue menyediakan O(log(n)) waktu untuk menambahkan dan metode polling dan O(1) untuk mendapatkan elemen minimal.