1. โครงสร้างข้อมูล PriorityQueue
โครงสร้างข้อมูลของ PriorityQueue (คิวลำดับความสำคัญ) ใน JDK7 เป็นกองไบนารี เพื่อความแม่นยำมันเป็นกองที่เล็กที่สุด
กองไบนารีเป็นกองพิเศษซึ่งเป็นต้นไม้ไบนารีที่สมบูรณ์ประมาณ กองไบนารีเป็นไปตามลักษณะ: ค่าคีย์ของโหนดพาเรนต์จะรักษาความสัมพันธ์ของคำสั่งซื้อคงที่กับค่าคีย์ของโหนดลูกใด ๆ และทรีย่อยด้านซ้ายและทรีย่อยด้านขวาของแต่ละโหนดเป็นกองไบนารี
ฮีปสูงสุดคือเมื่อค่าคีย์ของโหนดพาเรนต์มากกว่าหรือเท่ากับค่าคีย์ของโหนดเด็กใด ๆ ฮีปขั้นต่ำคือเมื่อค่าคีย์ของโหนดพาเรนต์น้อยกว่าหรือเท่ากับค่าคีย์ของโหนดเด็กใด ๆ
รูปต่อไปนี้เป็นกองสูงสุด
ส่วนหัวของทีม PriorityQueue เป็นองค์ประกอบที่เล็กที่สุดในลำดับที่กำหนด
PriorityQueue ไม่อนุญาตค่า NULL และไม่รองรับวัตถุที่ไม่สามารถเปรียบเทียบได้ PriorityQueue ต้องการการใช้อินเทอร์เฟซเปรียบเทียบและเปรียบเทียบเพื่อเรียงลำดับวัตถุและองค์ประกอบในพวกเขาจะถูกประมวลผลตามลำดับความสำคัญเมื่อเรียงลำดับ
ขนาดของ PriorityQueue นั้นไม่ได้ จำกัด แต่สามารถระบุขนาดเริ่มต้นได้เมื่อสร้างขึ้น เมื่อเพิ่มองค์ประกอบคิวคิวจะขยายโดยอัตโนมัติ
PriorityQueue ไม่ได้ปลอดภัยแบบเธรด PriorityBlockingQueue ที่คล้ายกันคือ Thread-Safe
เรารู้ว่าคิวเป็นไปตามโหมดแรกในครั้งแรก แต่บางครั้งวัตถุจำเป็นต้องดำเนินการตามลำดับความสำคัญในคิว ตัวอย่างเช่นเรามีแอปพลิเคชันที่สร้างรายงานหุ้นในช่วงเวลาทำการซื้อขายรายวันซึ่งต้องใช้การประมวลผลข้อมูลจำนวนมากและใช้เวลาในการประมวลผลเป็นจำนวนมาก เมื่อลูกค้าส่งคำขอไปยังแอปพลิเคชันนี้มันจะเข้าสู่คิว เราจำเป็นต้องจัดการกับลูกค้าลำดับความสำคัญก่อนและจากนั้นกับผู้ใช้ทั่วไป ในกรณีนี้ PriorityQueue ของ Java (คิวลำดับความสำคัญ) จะมีประโยชน์มาก
PriorityQueue เป็นคิวที่ไม่มีขอบเขตตามกองลำดับความสำคัญ องค์ประกอบในคิวลำดับความสำคัญนี้สามารถจัดเรียงตามธรรมชาติตามค่าเริ่มต้นหรือเรียงลำดับเมื่อคิวถูกสร้างอินสแตนซ์โดยตัวเปรียบเทียบที่ให้ไว้
คิวลำดับความสำคัญไม่อนุญาตค่า NULL และไม่รองรับวัตถุที่ไม่สามารถเทียบได้เช่นคลาสที่ผู้ใช้กำหนด คิวลำดับความสำคัญต้องการการใช้อินเทอร์เฟซ Java ที่เปรียบเทียบได้และตัวเปรียบเทียบเพื่อเรียงลำดับวัตถุและองค์ประกอบในนั้นจะถูกประมวลผลตามลำดับความสำคัญเมื่อเรียงลำดับ
ส่วนหัวของคิวลำดับความสำคัญเป็นองค์ประกอบที่เล็กที่สุดตามการเรียงลำดับตามธรรมชาติหรือการเรียงลำดับเปรียบเทียบ หากวัตถุหลายชิ้นมีการเรียงลำดับเดียวกันอาจเป็นไปได้ที่จะสุ่มใช้มัน เมื่อเราได้รับคิวเราจะส่งคืนวัตถุส่วนหัวของคิว
ขนาดของคิวลำดับความสำคัญนั้นไม่ จำกัด แต่สามารถระบุขนาดเริ่มต้นได้ในเวลาสร้าง เมื่อเราเพิ่มองค์ประกอบในคิวลำดับความสำคัญขนาดคิวจะเพิ่มขึ้นโดยอัตโนมัติ
PriorityQueue ไม่ปลอดภัยดังนั้น Java จึงจัดเตรียม priorityblockingqueue (การใช้อินเทอร์เฟซ BlockingQueue) สำหรับสภาพแวดล้อมแบบหลายเธรด Java
2. การวิเคราะห์ซอร์สโค้ด PriorityQueue
สมาชิก:
วัตถุชั่วคราว priavte [] คิว; ขนาด int ส่วนตัว = 0;
1. กระบวนการสร้างกองท็อปด้านบนขนาดเล็กโดย PriorityQueue
ที่นี่เราใช้ PriorityQueue Constructor เพื่อส่งผ่านคอนเทนเนอร์เป็นพารามิเตอร์ priorityQueue (collecntion <? ขยายตัวอย่าง e>:
กระบวนการสร้างกองด้านบนขนาดเล็กแบ่งออกเป็นสองขั้นตอน:
คัดลอกข้อมูลคอนเทนเนอร์และตรวจสอบว่าข้อมูลคอนเทนเนอร์เป็นโมฆะหรือไม่
ช่องว่างส่วนตัวเริ่มต้นจากการรวบรวม (คอลเลกชัน <? ขยาย e> c) {object [] a = c.toarray (); // ถ้า c.toarray ไม่ถูกต้องไม่คืนวัตถุ [] ให้คัดลอก if (a.getClass ()! = object []. class) a = array.copyof (a, a.length, object []. class); int len = a.length; if (len == 1 || this.Comparator! = null) สำหรับ (int i = 0; i <len; i ++) ถ้า (a [i] == null) โยน nullpointerexception ใหม่ (); this.queue = a; this.size = a.length;} ปรับเพื่อให้ข้อมูลเป็นไปตามโครงสร้างของกองเล็ก ๆ
ก่อนอื่นวิธีการปรับสองวิธี: siftup และ siftdown
Siftdown: เมื่อมีการกำหนดองค์ประกอบการเริ่มต้นองค์ประกอบควรได้รับการปรับเพื่อให้ตรงกับคุณสมบัติโครงสร้างของกองขั้นต่ำ ดังนั้นค่าคีย์ขององค์ประกอบ X จึงถูกเปรียบเทียบและแลกเปลี่ยนกับเด็กจากบนลงล่างอย่างต่อเนื่องจนกว่าจะพบว่าค่าคีย์ขององค์ประกอบ x น้อยกว่าหรือเท่ากับค่าคีย์ของเด็ก (นั่นคือรับประกันว่าจะมีขนาดเล็กกว่าค่าโหนดซ้ายและขวา)
ตัวอย่างเช่นดังที่แสดงในแผนภาพต่อไปนี้ปรับโหนดนี้ 9:
โมฆะส่วนตัว siftdowncomparable (int k, e x) {เทียบเท่า <? super e> key = (เปรียบเทียบ <? super e>) x; int ครึ่ง = ขนาด >>> 1; // size/2 เป็นตัวห้อยของโหนดใบแรก // ตราบใดที่โหนดใบยังไม่ถึงในขณะที่ (k <ครึ่ง) {int child = (k << 1) + 1; // ซ้ายวัตถุลูก c = คิว [เด็ก]; int ขวา = เด็ก + 1; // ค้นหาเด็กที่เล็กที่สุดและเล็กที่สุดของเด็กซ้ายและขวา (ขวา <size && ((เปรียบเทียบ <? super e>) c). compareto ((e) คิว [ขวา])> 0) c = คิว [child = ขวา]; if (key.compareto ((e) c) <= 0) break; คิว [k] = c; k = เด็ก; } คิว [k] = key;} SIFTUP: PriorityQueue แทรกองค์ประกอบใหม่ลงในหางทุกครั้งที่มีการเพิ่มองค์ประกอบใหม่ ดังนั้นจึงควรมีกระบวนการปรับเช่นเดียวกับ SIFTDOWN ยกเว้นเพื่อปรับจากด้านล่าง (ใบไม้) ขึ้นไป
ตัวอย่างเช่นกรอกโหนดด้วยคีย์ 3 ในแผนภาพต่อไปนี้:
โมฆะส่วนตัว siftupcomparable (int k, e x) {เทียบเท่า <? super e> key = (เปรียบเทียบ <? super e>) x; ในขณะที่ (k> 0) {int parent = (k - 1) >>> 1; // รับวัตถุตัวห้อยพาเรนต์ e = คิว [พาเรนต์]; if (key.Compareto ((e) e)> = 0) break; คิว [k] = e; k = ผู้ปกครอง; } คิว [k] = key;}กระบวนการโดยรวมของการสร้างกองชั้นบนขนาดเล็กคือ:
Void Private InitFromCollection (คอลเลกชัน <? ขยาย e> c) {เริ่มต้นจากการรวบรวม (C); หนัก(); -ในหมู่พวกเขา Heapify เป็นกระบวนการของ Siftdown
2. กระบวนการขยายความจุ PriorityQueue
ดังที่เห็นได้จากสมาชิกอินสแตนซ์ PriorityQueue เก็บรักษาวัตถุ [] ดังนั้นวิธีการขยายตัวของมันจึงคล้ายกับตารางคำสั่งซื้อ arraylist
เฉพาะซอร์สโค้ดของวิธีการเติบโตที่นี่
โมฆะส่วนตัวเติบโต (int mincapacity) {int oldcapacity = queue.length; // ขนาดสองเท่าถ้าเล็ก; เพิ่มขึ้นอีก 50% int newcapacity = oldcapacity + ((ความเป็นไปได้ <64)? (OldCapacity + 2): (OldCapacity >> 1)); // รหัสที่ใส่ใจมากเกินไปถ้า (newCapacity - max_array_size> 0) newCapacity = hugecapacity (mincapacity); queue = arrays.copyof (คิว, newcapacity); -จะเห็นได้ว่าเมื่อความสามารถของอาร์เรย์ไม่ใหญ่ความสามารถจะไม่ใหญ่ทุกครั้ง เมื่อความจุอาเรย์มากกว่า 64 จะขยายสองเท่าในแต่ละครั้ง
3. แอปพลิเคชัน PriorityQueue
EG1:
นี่คือแอปพลิเคชันที่ง่ายที่สุด: ค้นหาจำนวนที่ใหญ่ที่สุด K-Th จากข้อมูลแบบไดนามิก
ความคิดคือการรักษากองด้านบนขนาดเล็กที่มีขนาด = k
// data เป็นข้อมูลแบบไดนามิก // heap เก็บรักษาข้อมูลแบบไดนามิก // res ใช้เพื่อบันทึกค่า k-most public boolean kthlargest (int data, int k, priorityqueue <integer> heap, int [] res) {ถ้า (heap.size () <k) {heap.offer (data); if (heap.size () == k) {res [0] = heap.peek (); กลับมาจริง; } return false; } if (heap.peek () <data) {heap.poll (); HEAP.OFFER (ข้อมูล); } res [0] = heap.peek (); กลับมาจริง; -
EG2:
เรามีลูกค้าชั้นเรียนผู้ใช้ซึ่งไม่ได้จัดเรียงใด ๆ เมื่อเราใช้เพื่อสร้างคิวลำดับความสำคัญเราควรจัดเตรียมวัตถุเปรียบเทียบ
customer.java
แพ็คเกจ com.journaldev.collections; ลูกค้าชั้นเรียนสาธารณะ {ID INT ส่วนตัว; ชื่อสตริงส่วนตัว; ลูกค้าสาธารณะ (int i, string n) {this.id = i; this.name = n; } สาธารณะ int getId () {return id; } สตริงสาธารณะ getName () {ชื่อคืน; - เราใช้หมายเลขสุ่ม Java เพื่อสร้างวัตถุผู้ใช้แบบสุ่ม สำหรับการเรียงลำดับตามธรรมชาติเราใช้วัตถุจำนวนเต็มซึ่งเป็นวัตถุ Java ที่ห่อหุ้มด้วย
นี่คือรหัสทดสอบขั้นสุดท้ายที่แสดงวิธีการใช้ PriorityQueue:
PriorityQueueExample.java
แพ็คเกจ com.journaldev.collections; นำเข้า java.util.Comparator; นำเข้า Java.util.priorityqueue; นำเข้า java.util.queue; นำเข้า Java.util.random; ระดับสาธารณะ PriorityQueueUeExample {โมฆะคงที่สาธารณะหลัก (String [] args) {// ลำดับความสำคัญคิวการเรียงลำดับตามธรรมชาติการเรียงลำดับคิว <จำนวนเต็ม> จำนวนเต็ม = new PriorityQueue <> (7); สุ่มแรนด์ = ใหม่สุ่ม (); สำหรับ (int i = 0; i <7; i ++) {IntegerPriorityQueue.add (จำนวนเต็มใหม่ (rand.Nextint (100))); } สำหรับ (int i = 0; i <7; i ++) {จำนวนเต็มใน = integerPriorityQueue.poll (); System.out.println ("การประมวลผลจำนวนเต็ม:"+in); } // การใช้คิวลำดับความสำคัญตัวอย่างคิว <ลูกค้า> ลูกค้า PriorityQueue = ใหม่ PriorityQueue <> (7, IDComparator); Adddatatoqueue (ลูกค้าผู้มีอำนาจ); PolldataFromqueue (ลูกค้าผู้มีอำนาจ); } // ตัวเปรียบเทียบที่ไม่ระบุตัวตนใช้ตัวเปรียบเทียบแบบคงที่สาธารณะ <ลูกค้า> idComparator = ใหม่ตัวเปรียบเทียบ <ลูกค้า> () {@Override สาธารณะ int เปรียบเทียบ (ลูกค้า C1, ลูกค้า C2) {return (int) (c1.getId () - c2.getId ()); - // วิธีการสากลที่ใช้ในการเพิ่มข้อมูลไปยังคิวส่วนตัวคงที่คงที่ adddatatoqueue (คิว <ลูกค้า> ลูกค้าผู้มีความเป็นลูกค้า) {สุ่มแรนด์ = ใหม่สุ่ม (); สำหรับ (int i = 0; i <7; i ++) {int id = rand.nextint (100); Customer-eriorityQueue.add (ลูกค้าใหม่ (ID, "Pankaj"+ID)); }} // วิธีการทั่วไปสำหรับการดึงข้อมูลจากคิวโมฆะส่วนตัวแบบคงที่ polldataFromqueue (คิว <ลูกค้า> ลูกค้าผู้มีอำนาจ) {ในขณะที่ (จริง) {ลูกค้า cust = ลูกค้า ถ้า (cust == null) break; System.out.println ("การประมวลผลลูกค้าด้วย id ="+cust.getId ()); - โปรดทราบว่าฉันใช้คลาส Java ที่ไม่ระบุชื่อซึ่งใช้อินเทอร์เฟซเปรียบเทียบและใช้ตัวเปรียบเทียบที่ใช้ ID
เมื่อฉันเรียกใช้โปรแกรมทดสอบด้านบนฉันได้รับผลลัพธ์ต่อไปนี้:
การประมวลผลจำนวนเต็ม: 9 การประมวลผลจำนวนเต็ม: 16 การประมวลผลจำนวนเต็ม: 18 การประมวลผลจำนวนเต็ม: จำนวนเต็ม 25 การประมวลผล: 33 การประมวลผลจำนวนเต็ม: 75 การประมวลผลจำนวนเต็ม: 77 การประมวลผลลูกค้าด้วยการประมวลผลลูกค้าด้วยการประมวลผลลูกค้าด้วย ID = 20 การประมวลผลลูกค้า id = 82 การประมวลผลลูกค้าด้วย id = 96
จากผลลัพธ์ผลลัพธ์จะเห็นได้ชัดว่าองค์ประกอบที่เล็กที่สุดจะถูกนำออกมาก่อนที่หัวของคิว หากไม่ได้ใช้งานตัวเปรียบเทียบ ClassCastException จะถูกโยนลงเมื่อสร้างความเป็นลูกค้าของลูกค้า
ข้อยกเว้นในด้าย "หลัก" java.lang.classcastexception: com.journalev.collections.customer ไม่สามารถส่งไปที่ java.lang.comparable ที่ java.util.priorityqueue.siftupcomparable java.util.priorityqueue.offer (priorityqueue.java:329) ที่ java.util.priorityqueue.add (priorityqueue.java:306) ที่ com.journalev.collections com.journaldev.collections.priorityqueueexample.main (priorityqueueuexample.java:25)