Java Priority Queue: bukan baris gilir klasik

Dalam artikel ini kita mempelajari baris gilir keutamaan, kelas Java, yang melaksanakan antara muka Giliran. Apakah yang diketahui oleh pengaturcara tentang Antara Muka Baris Biasa? Pertama sekali, antara muka ini adalah berdasarkan prinsip FIFO atau “first in first out”. Itu mengingatkan baris gilir biasa dalam maksud biasa. Anda ingin mendapatkan kopi dari McDrive? Jika kereta anda adalah yang pertama berhampiran tingkap, anda akan mendapatkan kopi anda sebelum pemandu yang seterusnya.

Pengisytiharan Antara Muka Baris

public interface Queue<E> extends Collection<E>

Apakah itu Barisan Keutamaan

Apakah Barisan Keutamaan? Pertama sekali ia adalah kelas yang melaksanakan antara muka Baris dalam kes memasukkan elemen dari belakang dan mengeluarkan elemen dari kepala. Namun ia bukan barisan biasa di dalam. Susunan elemen baris gilir keutamaan Java bergantung pada keutamaan elemen. Elemen dengan keutamaan tertinggi akan dialihkan ke kepala baris gilir. Jika anda memadamkan (menyajikan) elemen kedudukan tertinggi, elemen kedua pergi ke kepala untuk mendapatkan kopinya. Bagaimanakah keutamaan ditentukan? Menurut dokumentasi, elemen baris gilir keutamaan disusun mengikut susunan semula jadinya, atau oleh Pembanding yang disediakan pada masa pembinaan baris gilir, bergantung pada pembina yang digunakan. Baris gilir keutamaan berdasarkan timbunan min keutamaan. Ini bermakna, dalam kes elemen baris gilir nombor, elemen pertama baris gilir akan menjadi yang minimum daripada nombor ini. Selalunya selepas membaca definisi ini, pelajar baru mula berfikir bahawa baris gilir keutamaan disusun dalam erti kata yang linear. Iaitu, jika, katakan, kita menggunakan baris gilir yang unsur-unsurnya adalah nombor asli, maka elemen pertama akan menjadi yang terkecil, dan yang terakhir - yang terbesar. Ini tidak sepenuhnya benar. Untuk memahami cara barisan keutamaan berfungsi sebenarnya dan apa yang diberikannya, anda perlu memikirkan cara timbunan berfungsi. Kami menganggap struktur dalaman baris gilir keutamaan menggunakan contoh sedikit kemudian. Sekarang mari kita fikirkan sifat luarannya. maka elemen pertama akan menjadi yang terkecil, dan yang terakhir - yang terbesar. Ini tidak sepenuhnya benar. Untuk memahami cara barisan keutamaan berfungsi sebenarnya dan apa yang diberikannya, anda perlu memikirkan cara timbunan berfungsi. Kami menganggap struktur dalaman baris gilir keutamaan menggunakan contoh sedikit kemudian. Sekarang mari kita fikirkan sifat luarannya. maka elemen pertama akan menjadi yang terkecil, dan yang terakhir - yang terbesar. Ini tidak sepenuhnya benar. Untuk memahami cara barisan keutamaan berfungsi sebenarnya dan apa yang diberikannya, anda perlu memikirkan cara timbunan berfungsi. Kami menganggap struktur dalaman baris gilir keutamaan menggunakan contoh sedikit kemudian. Sekarang mari kita fikirkan sifat luarannya.

Pembina dan pengisytiharan kelas PriorityQueue

Kelas PriorityQueue menyediakan 6 cara berbeza untuk membina baris gilir keutamaan dalam Java.

• PriorityQueue() - baris gilir kosong dengan kapasiti awal lalai (11) yang menyusun elemennya mengikut susunan semula jadinya.
• PriorityQueue(Collection c) - baris gilir kosong yang mengandungi elemen dalam koleksi yang ditentukan.
• PriorityQueue(int initialCapacity) - baris gilir kosong dengan kapasiti awal yang ditentukan yang menyusun elemennya mengikut susunan semula jadinya.
• PriorityQueue(int initialCapacity, Comparator comparator) - baris gilir kosong dengan kapasiti awal yang ditentukan yang menyusun elemennya mengikut pembanding yang ditentukan.
• PriorityQueue(PriorityQueue c) - baris gilir kosong yang mengandungi elemen dalam baris gilir keutamaan yang ditentukan.
• PriorityQueue(SortedSet c) - baris gilir kosong yang mengandungi elemen dalam set diisih yang ditentukan.

Barisan Keutamaan dalam Java diisytiharkan dengan cara seterusnya:

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

Mencipta PriorityQueue

Mari buat baris gilir keutamaan integer. Pelaksanaan Barisan Keutamaan, kod Java:

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

Kami telah mencipta baris gilir keutamaan tanpa hujah. Dalam kes ini, ketua baris gilir keutamaan ialah bilangan minimum baris gilir. Jika anda mengeluarkan kepala, elemen terkecil seterusnya akan mengambil tempat ini. Jadi anda boleh mengalih keluar elemen daripada baris gilir dalam tertib menaik. Jika perlu anda boleh menukar prinsip pesanan menggunakan antara muka Comparator.

Kaedah Java PriorityQueue

Kelas Java PriorityQueue mempunyai kaedah penting untuk menambah, mengalih keluar dan menyemak elemen.

Masukkan Elemen ke dalam Barisan Keutamaan

• boolean add(objek) memasukkan elemen yang ditentukan ke dalam baris gilir keutamaan. Kembali benar sekiranya berjaya. Jika baris gilir penuh, kaedah membuang pengecualian.
• tawaran boolean(objek) memasukkan elemen yang ditentukan ke dalam baris gilir keutamaan ini. Jika baris gilir penuh, kaedah mengembalikan palsu.

Anda boleh menggunakan kedua-dua operasi menambah, tiada perbezaan untuk kebanyakan kes. Berikut ialah contoh kecil permulaan dan penambahan elemen ke dalam baris gilir keutamaan.

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 ialah:

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

Susunan unsur-unsur itu nampaknya pelik, kami akan menerangkannya kemudian.

Mendapatkan semula dan mengalih keluar elemen daripada Barisan Keutamaan

• boolean remove(object) mengalih keluar satu contoh elemen yang ditentukan daripada baris gilir ini, jika ia ada.
• Tinjauan objek() mengambil dan mengalih keluar kepala baris gilir ini. Mengembalikan batal jika baris gilir kosong.
• void clear() mengalih keluar semua elemen daripada baris gilir keutamaan.
• Elemen objek() mendapatkan semula kepala baris gilir ini tanpa mengalihkannya. Membuang NoSuchElementException jika baris gilir kosong.
• Object peek() mendapatkan semula kepala baris gilir tanpa mengalihkannya. Mengembalikan batal jika baris gilir 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());
    }
}

Keluaran:

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, cuba mencetak kepala Baris kosong menggunakan kaedah element() membawa kepada NoSuchElementexception .

Pembanding PriorityQueue

• Comparator comparator() mengembalikan comparator yang digunakan untuk memesan elemen dalam baris gilir. Mengembalikan null jika baris gilir diisih mengikut susunan semula jadi elemennya.

Barisan keutamaan Java, contoh dengan pembanding

Kami menggunakan susunan semula jadi (menaik) dalam contoh kod di atas, tetapi kadangkala kami harus mengubahnya. Berikut ialah contoh baris gilir keutamaan Java, di mana kami mencipta kelas pembanding dalaman kami sendiri yang melaksanakan antara muka Comparator. Pembanding kami akan menyusun elemen daripada yang terbesar kepada 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;
        }
    }
}

Keluaran:

the head of Queue = 5
5
4
3
2
1

Ketua Baris Gilir sekarang bukanlah elemen minimum, tetapi maksima, dan susunan telah ditukar kepada terbalik.

Mengulangi PriorityQueue menggunakan iterator

ProrityQueue ialah sebahagian daripada rangka kerja Koleksi dan melaksanakan antara muka Iterable<> . Untuk mengulangi elemen baris gilir keutamaan anda boleh menggunakan kaedah iterator() . Berikut adalah contoh:

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

Keluaran:

1 2 4 5 3 

Lebih banyak kaedah PriorityQueue

• boolean mengandungi(Objek o) mengembalikan benar jika baris gilir mengandungi elemen o.
• int size() mengembalikan bilangan elemen dalam baris gilir ini.
• Object[] toArray() mengembalikan tatasusunan yang mengandungi semua elemen dalam baris gilir ini.

Berikut adalah contoh:

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

Keluaran:

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 priorityqueue java 8, anda akan dapati di sana definisi seterusnya: Barisan keutamaan yang tidak terhad berdasarkan timbunan keutamaan. Unsur-unsur baris gilir keutamaan disusun mengikut susunan semula jadinya, atau oleh Pembanding yang disediakan pada masa pembinaan baris gilir, bergantung pada pembina yang digunakan. Barisan keutamaan tidak membenarkan unsur nol. Barisan keutamaan yang bergantung pada susunan semula jadi juga tidak membenarkan pemasukan objek yang tidak setanding (berbuat demikian boleh mengakibatkan ClassCastException). Heap ialah perkataan yang sangat penting di sini. Ia menerangkan sifat susunan elemen Baris Keutamaan.

Prinsip kerja PriorityQueue: Binary Heap

Mari kita mulakan dengan contoh. Mari kita cipta dua objek yang melaksanakan antara muka Baris Gilir. Salah satunya LinkedList, yang kedua — PriorityQueue. Kedua-duanya mempunyai 5 elemen Integer (1,2,3,4 dan 5) dan kami mula meletakkan elemen ke dalam baris gilir kami dari yang terbesar hingga yang terkecil. Jadi, yang pertama datang 5, kemudian 4, 3, 2 dan yang terakhir akan menjadi 1. Kemudian cetak kedua-dua senarai untuk menyemak pesanan keluar.

   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 kerja kod ini adalah yang berikut:

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

Nah, susunan senarai terpaut boleh diramal dan difahami. Ia diperintahkan mengikut prinsip FIFO. Kami bermula dengan 5, jadi elemen ini adalah yang pertama dalam barisan, kemudian pergi ke 4 dan seterusnya. Apakah yang boleh kami beritahu tentang susunan baris gilir keutamaan? Docs mengatakan bahawa elemen baris gilir keutamaan disusun mengikut susunan semula jadinya, atau oleh Pembanding yang disediakan pada masa pembinaan baris gilir. Walau bagaimanapun, susunan ini nampaknya tidak "semula jadi" dalam makna pengisihan linear. Kami lebih suka mengharapkan [1, 2, 3, 4, 5], bukan [1, 2, 4, 5, 3]. Untuk memahami mengapa susunan mendapatkan semula adalah seperti itu, kita harus mengingati baris gilir keutamaan berdasarkan timbunan. Apakah timbunan itu? Ia adalah struktur data berdasarkan pokok binari. Sifat utama timbunan: keutamaan setiap ibu bapa adalah lebih besar daripada keutamaan anak-anaknya. Biar saya ingatkan anda bahawa pokok dipanggil binari lengkap jika setiap ibu bapa mempunyai tidak lebih daripada dua anak, dan pengisian tahap pergi dari atas ke bawah (dari tahap yang sama — dari kiri ke kanan). Timbunan binari menyusun semula dirinya setiap kali elemen ditambah atau dialih keluar daripadanya. Dalam kes timbunan min, elemen terkecil pergi ke akar tanpa mengira susunan sisipannya. Baris gilir keutamaan berdasarkan timbunan min ini. Ini bermakna, dalam kes elemen baris gilir nombor, elemen baris gilir pertama akan menjadi nombor minimum bagi nombor ini. Jika anda memadamkan akar, yang terkecil seterusnya menjadi akar.

Mari kita beralih kepada contoh kita.

Langkah 1. Kami meletakkan '5' ke dalam barisan keutamaan. Ia menjadi akar. Langkah 2. Kami menambah '4' ke dalam baris gilir keutamaan. 4 <5, jadi elemen baharu harus lebih tinggi daripada elemen yang lebih lama. Yang 4 menjadi akar, 5 adalah anak kirinya. Sekarang struktur data dalam Java ialah [4, 5] Langkah 3. Kami menambah '3'. Buat sementara waktu ia menjadi anak kanan akar (4). Walau bagaimanapun, 3 < 4, jadi kita harus mengangkatnya. Pertukaran 3 dan 4. Sekarang kita mempunyai struktur seperti [3, 5, 4] Langkah 4. Kita tambah '2'. Ia menjadi anak kiri 5. 2<5, jadi tukarkan mereka. 2 menjadi anak kiri 3, 2 < 3, jadi satu lagi proses pertukaran. Sekarang kita mempunyai struktur [2,3,4,5] Langkah 5.Kami menambah '1'. Ia datang dari anak kanan 3 ke anak kiri 2, dan kemudian pergi ke akar. Struktur data hasil: [1,2,4,5,3] Proses Pembuangan bermula dari akar, dan ia mencetuskan prosedur terbalik. Jadi, mula-mula kita mempunyai 1 sebagai akar, kemudian 2, 3, 4 dan akhirnya 5. Itulah sebabnya menggunakan operasi mengalih keluar poll()

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

kami telah "diisih" dalam output sen linear:

1
2
3
4
5

Jadi baris gilir keutamaan boleh berkesan untuk beberapa operasi. Ia mengambil masa O(log N) untuk memasukkan dan memadam setiap elemen, dan anda boleh mendapatkan elemen minimum dalam O(1). Berikut adalah contoh penuh:

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

Adalah penting untuk memahami bahawa baris gilir keutamaan adalah berdasarkan timbunan binari, jadi mereka tidak menyimpan elemen dalam susunan disusun linear. Setiap jalan dari akar ke daun disusun, tetapi cara yang berbeza dari akar tidak. Ini bermakna anda boleh mendapatkan elemen minimum baris gilir dengan cepat.

Perkara yang anda perlu tahu tentang baris gilir keutamaan. Senarai ringkas

• Barisan Keutamaan tidak membenarkan objek NULL.
• Anda boleh menambah hanya objek yang setanding ke dalam PriorityQueue.
• Barisan keutamaan dibina sebagai timbunan min, sejenis pokok binari. Elemen minimum ialah akar. Objek baris gilir keutamaan disusun secara lalai dalam susunan semula jadi.
• Anda boleh menggunakan Comparator jika anda memerlukan pesanan tersuai.
• PriorityQueue tidak selamat untuk thread, jadi lebih baik anda menggunakan PriorityBlockingQueue untuk bekerja dalam persekitaran serentak.
• PriorityQueue menyediakan masa O(log(n)) untuk kaedah tambah dan tinjauan pendapat dan O(1) untuk mendapatkan elemen minimum.