1. Struktur data prioritas
Struktur data prioritas (antrian prioritas) di JDK7 adalah tumpukan biner. Tepatnya, ini adalah tumpukan terkecil.
Tumpukan biner adalah tumpukan khusus, yang kira -kira merupakan pohon biner lengkap. Tumpukan biner memenuhi karakteristik: Nilai kunci dari simpul induk selalu mempertahankan hubungan pesanan tetap dengan nilai kunci dari setiap node anak, dan subtree kiri dan subtree kanan masing -masing node adalah tumpukan biner.
Tumpukan maksimum adalah ketika nilai kunci dari simpul induk selalu lebih besar dari atau sama dengan nilai kunci dari setiap node anak. Tumpukan minimum adalah ketika nilai kunci dari simpul induk selalu kurang dari atau sama dengan nilai kunci dari setiap node anak.
Gambar berikut adalah tumpukan maksimum
PriityQueue Team Header adalah elemen terkecil dalam urutan yang diberikan.
PriityQueue tidak memungkinkan nilai nol dan tidak mendukung objek yang tidak rumit. PriityQueue mensyaratkan penggunaan antarmuka yang sebanding dan komparator untuk mengurutkan objek, dan elemen -elemen di dalamnya akan diproses sesuai dengan prioritas saat menyortir.
Ukuran prioritas tidak terbatas, tetapi ukuran awal dapat ditentukan saat dibuat. Saat menambahkan elemen antrian, antrian akan mengembang secara otomatis.
PriityQueue tidak aman-utas, priorityblockingQueue yang serupa adalah aman-aman.
Kita tahu bahwa antrian mengikuti mode pertama di pertama, tetapi kadang-kadang objek perlu diproses berdasarkan prioritas dalam antrian. Misalnya, kami memiliki aplikasi yang menghasilkan laporan saham selama jam perdagangan harian, yang membutuhkan pemrosesan banyak data dan membutuhkan banyak waktu pemrosesan. Ketika klien mengirimkan permintaan ke aplikasi ini, itu benar -benar memasuki antrian. Kita perlu berurusan dengan pelanggan prioritas terlebih dahulu dan kemudian dengan pengguna biasa. Dalam hal ini, prioritas Java (antrian prioritas) akan sangat membantu.
PriityQueue adalah antrian yang tidak terikat berdasarkan tumpukan prioritas. Elemen -elemen dalam antrian prioritas ini dapat diurutkan secara alami secara default atau diurutkan ketika antrian dipakai oleh pembanding yang disediakan.
Antrian prioritas tidak mengizinkan nilai nol dan tidak mendukung objek yang tidak rumit, seperti kelas yang ditentukan pengguna. Antrian prioritas membutuhkan penggunaan antarmuka Java yang sebanding dan pembanding untuk mengurutkan objek, dan elemen -elemen di dalamnya akan diproses sesuai dengan prioritas saat menyortir.
Header dari antrian prioritas adalah elemen terkecil berdasarkan penyortiran alami atau penyortiran pembanding. Jika banyak objek memiliki jenis yang sama, dimungkinkan untuk mengambil salah satu dari mereka. Saat kita mendapatkan antrian, kita mengembalikan objek header antrian.
Ukuran antrian prioritas tidak terbatas, tetapi ukuran awal dapat ditentukan pada waktu penciptaan. Ketika kami menambahkan elemen ke antrian prioritas, ukuran antrian akan meningkat secara otomatis.
PriityQueue tidak aman, jadi Java menyediakan prioritasblockingqueue (menerapkan antarmuka blockingqueue) untuk lingkungan multi-utma java.
2. Analisis Kode Sumber Prioritas
anggota:
objek transien priavte [] antrian; ukuran int pribadi = 0;
1. Proses membangun tumpukan atas kecil berdasarkan prioritas
Di sini kami menggunakan PriityQueue Constructor untuk meneruskan dalam wadah sebagai prioritas parameter (Collecntion <? Extends e> Contoh:
Proses membangun tumpukan atas kecil secara kasar dibagi menjadi dua langkah:
Salin data kontainer dan periksa apakah data kontainernya nol
Private Void InitElementsFromCollection (Collection <? Extends e> c) {objek [] a = c.toArray (); // Jika c.toarray salah tidak mengembalikan objek [], salin. if (a.getClass ()! = Object []. Class) a = arrays.copyof (a, a.length, objek []. class); int len = a.length; if (len == 1 || ini. this.queue = a; this.size = a.length;} Sesuaikan untuk membuat data memenuhi struktur tumpukan atas kecil.
Pertama, dua metode penyesuaian: siftup dan siftdown
Siftown: Ketika elemen inisialisasi diberikan, elemen harus disesuaikan sehingga memenuhi sifat struktural dari tumpukan minimum. Oleh karena itu, nilai kunci elemen X secara konstan dibandingkan dan dipertukarkan dengan anak dari atas ke bawah sampai ditemukan bahwa nilai kunci elemen x kurang dari atau sama dengan nilai kunci anak (yaitu, dijamin lebih kecil dari nilai simpul kiri dan kanan), atau jatuh ke simpul daun.
Misalnya, seperti yang ditunjukkan pada diagram berikut, sesuaikan simpul ini 9:
Private void siftdowncomparable (int k, e x) {sebanding <? super e> key = (sebanding <? super e>) x; int setengah = ukuran >>> 1; // size/2 adalah subskrip dari simpul daun pertama // selama simpul daun tidak tercapai sementara (k <setengah) {int child = (k << 1) + 1; // meninggalkan objek anak C = antrian [anak]; int right = anak + 1; // Cari tahu anak -anak terkecil dan terkecil dari anak -anak kiri dan kanan (kanan <size && ((sebanding <? Super e>) c) .compareto ((e) antrian [kanan])> 0) c = antrian [anak = kanan]; if (key.compareto ((e) c) <= 0) break; antrian [k] = c; k = anak; } antrian [k] = key;} Siftup: PriityQueue memasukkan elemen baru ke dalam ekor setiap kali elemen baru ditambahkan. Oleh karena itu, harus ada proses penyesuaian yang sama dengan siftdown, kecuali untuk menyesuaikan dari bawah (daun) ke atas.
Misalnya, isi simpul dengan kunci 3 dalam diagram berikut:
Private void siftupcomparable (int k, e x) {sebanding <? super e> key = (sebanding <? super e>) x; while (k> 0) {int parent = (k - 1) >>> 1; // Dapatkan Objek Subskrip Induk E = Antrian [Parent]; if (key.compareto ((e) e)> = 0) break; antrian [k] = e; k = induk; } antrian [k] = key;}Proses keseluruhan membangun tumpukan atas kecil adalah:
private void initfromCollection (collection <? Extends e> c) {initElementsfromCollection (c); berat(); }Di antara mereka, Heapify adalah proses siftdown.
2. Proses Perluasan Kapasitas Prioritas
Seperti yang dapat dilihat dari anggota instance, PriityQueue memelihara objek [], sehingga metode perluasannya mirip dengan daftar array tabel pesanan.
Hanya kode sumber metode Grow yang diberikan di sini
private void grow (int mincapacity) {int oldcapacity = queue.length; // ukuran ganda jika kecil; lain tumbuh sebesar 50% int newcapacity = oldcapacity + ((oldcapacity <64)? (oldcapacity + 2): (oldcapacity >> 1)); // kode overflow -sadar jika (newcapacity - max_array_size> 0) newCapacity = hugeCapacity (minsapacity); antrian = arrays.copyof (antrian, newcapacity); }Dapat dilihat bahwa ketika kapasitas array tidak besar, kapasitasnya tidak besar setiap saat. Ketika kapasitas array lebih besar dari 64, ganda diperluas setiap kali.
3. Aplikasi Prioritas
EG1:
Berikut adalah aplikasi paling sederhana: temukan angka terbesar K-th dari data dinamis.
Idenya adalah untuk mempertahankan tumpukan atas kecil dengan ukuran = k.
// Data adalah data dinamis // heap memelihara data dinamis // res digunakan untuk menyimpan nilai kthlar terbesar nilai kthlarean (int k, priityqueue <integer> heap, int [] res) {if (heap.size () <k) {heap.offer (data); if (heap.size () == k) {res [0] = heap.peek (); Kembali Benar; } return false; } if (heap.peek () <data) {heap.poll (); heap.offer (data); } res [0] = heap.peek (); Kembali Benar; }
EG2:
Kami memiliki pelanggan kelas pengguna yang tidak menyediakan jenis apa pun. Ketika kami menggunakannya untuk membuat antrian prioritas, kami harus menyediakannya dengan objek pembanding.
Customer.java
paket com.journaldev.collections; Pelanggan kelas publik {private int id; nama string pribadi; Pelanggan publik (int i, string n) {this.id = i; this.name = n; } public int getId () {return id; } public string getName () {return name; }} Kami menggunakan nomor acak java untuk menghasilkan objek pengguna acak. Untuk penyortiran alami, kami menggunakan objek Integer, yang juga merupakan objek Java yang dienkapsulasi.
Berikut adalah kode uji akhir yang menunjukkan cara menggunakan prioritas:
PrioritasqueueExample.java
paket com.journaldev.collections; impor java.util.comparator; impor java.util.priorityqueue; impor java.util.queue; impor java.util.random; Public Class PriityqueEExample {public static void main (string [] args) {// antrian prioritas Contoh penyortiran alami antrian <Integer> integerpriorityqueue = prioritas baru <> (7); Rand acak = acak baru (); untuk (int i = 0; i <7; i ++) {integerpriorityqueue.add (integer baru (rand.nextint (100))); } untuk (int i = 0; i <7; i ++) {integer in = integerpriorityqueue.poll (); System.out.println ("Processing Integer:"+in); } // Contoh Penggunaan Antrian Prioritas Antrian <sustomer> CustomerPriorityQueue = New PriityQueue <> (7, IDComparator); addDatoQueueUe (customerpriorityqueue); PollDataFromQueue (customerpriorityqueue); } // Komparator Anonim mengimplementasikan komparator statis publik <sust customer> idpompeparator = pembanding baru <sust customer> () {@Override public int compare (pelanggan C1, pelanggan C2) {return (int) (c1.getId () - c2.getid ()); }}; // Metode universal yang digunakan untuk menambahkan data ke antrian private static void addDatatoqueUe (antrian <sust customer> customerpriorityqueue) {acak rand = new random (); untuk (int i = 0; i <7; i ++) {int id = rand.nextint (100); customerpriorityqueue.add (pelanggan baru (id, "pankaj"+id)); }} // Metode umum untuk mengambil data dari antrian private static void pollDataFromQueue (antrian <sust customer> customerpriorityqueue) {while (true) {customer cust = customerpriorityqueue.poll (); if (cust == null) break; System.out.println ("Memproses Pelanggan dengan ID ="+cust.getId ()); }}}} Perhatikan bahwa saya menggunakan kelas anonim Java yang mengimplementasikan antarmuka pembanding dan mengimplementasikan pembanding berbasis ID.
Ketika saya menjalankan program pengujian di atas, saya mendapatkan output berikut:
Processing Integer: 9 Prosesing Integer: 16 Prosesing Integer: 18 Prosesing Integer: 25 Processing Integer: 33 Processing Integer: 75 Processing Integer: 77 Prosesing Pelanggan dengan Id Pelanggan = Pelanggan 28 dengan Idprocessing Pelanggan dengan Idprocesing dengan Idprocesing dengan Idprocesing dengan Idprocesing dengan Id Customer = 20 Processing dengan Id Customer dengan Idprocesing dengan ID = 247 dengan Idprocesing dengan Idprocesing dengan Idprocesing dengan Id Customer dengan ID = 24 Id Customer dengan ID = 24 Id Customer dengan Ids = ID = 82 PROKESSING PELANGGAN DENGAN ID = 96
Dari hasil output, dapat terlihat jelas bahwa elemen terkecil kemudian dikeluarkan terlebih dahulu di kepala antrian. Jika pembanding tidak diimplementasikan, ClassCastException akan dilemparkan saat membuat CustomerPriorityQueue.
Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633) at java.util.PriorityQueue.siftUp(PriorityQueue.java:629) at java.util.priorityqueue.offer (prioritasqueue.java:329) di java.util.priorityqueue.add (prioritasqueue.java:306) di com.journaldev.collections.priorityquexample.adddatatoqueue (priewiityquelex. com.journaldev.collections.priorityqueueExample.main (priityqueueExample.java:25)