ในบทความนี้ เราเรียนรู้คิวลำดับความสำคัญ คลาส Java ที่ใช้อินเทอร์เฟซคิว โปรแกรมเมอร์รู้อะไรเกี่ยวกับ Queue Interface ปกติ ก่อนอื่น อินเทอร์เฟซนี้ใช้หลักการ FIFO หรือ “เข้าก่อนออกก่อน” นั่นเตือนคิวปกติในความหมายทั่วไป คุณต้องการรับกาแฟจาก McDrive หรือไม่? หากรถของคุณเป็นคันแรกใกล้หน้าต่าง คุณจะได้กาแฟก่อนคนขับที่อยู่ถัดไป
Priority Queue คืออะไร? ประการแรกคือคลาสที่ใช้อินเทอร์เฟซคิวในกรณีที่แทรกองค์ประกอบจากด้านหลังและลบองค์ประกอบออกจากส่วนหัว อย่างไรก็ตามไม่ใช่คิวปกติภายใน ลำดับของอิลิเมนต์ลำดับความสำคัญของ Java ขึ้นอยู่กับลำดับความสำคัญของอิลิเมนต์ องค์ประกอบที่มีลำดับความสำคัญสูงสุดจะถูกย้ายไปที่ส่วนหัวของคิว หากคุณลบ (เสิร์ฟ) องค์ประกอบอันดับสูงสุด องค์ประกอบที่สองจะไปที่ส่วนหัวเพื่อรับกาแฟ กำหนดลำดับความสำคัญอย่างไร? ตามเอกสารประกอบ องค์ประกอบของคิวลำดับความสำคัญจะถูกจัดลำดับตามลำดับธรรมชาติ หรือโดยตัวเปรียบเทียบที่มีให้ในเวลาสร้างคิว ขึ้นอยู่กับตัวสร้างที่ใช้ คิวลำดับความสำคัญขึ้นอยู่กับฮีปขั้นต่ำลำดับความสำคัญ นั่นหมายความว่า ในกรณีขององค์ประกอบคิวตัวเลข องค์ประกอบแรกของคิวจะเป็นจำนวนที่น้อยที่สุด บ่อยครั้งหลังจากอ่านคำนิยามนี้ นักเรียนมือใหม่เริ่มคิดว่าคิวลำดับความสำคัญถูกจัดเรียงในลักษณะเส้นตรง นั่นคือถ้าเราใช้คิวที่มีองค์ประกอบเป็นจำนวนธรรมชาติองค์ประกอบแรกจะเล็กที่สุดและองค์ประกอบสุดท้ายจะใหญ่ที่สุด สิ่งนี้ไม่เป็นความจริงทั้งหมด เพื่อทำความเข้าใจว่าคิวลำดับความสำคัญทำงานอย่างไรและให้อะไร คุณต้องเข้าใจว่าฮีปทำงานอย่างไร เราจะพิจารณาโครงสร้างภายในของลำดับความสำคัญโดยใช้ตัวอย่างในภายหลัง ทีนี้มาดูคุณสมบัติภายนอกกัน จากนั้นองค์ประกอบแรกจะเล็กที่สุดและองค์ประกอบสุดท้ายจะใหญ่ที่สุด สิ่งนี้ไม่เป็นความจริงทั้งหมด เพื่อทำความเข้าใจว่าคิวลำดับความสำคัญทำงานอย่างไรและให้อะไร คุณต้องเข้าใจว่าฮีปทำงานอย่างไร เราจะพิจารณาโครงสร้างภายในของลำดับความสำคัญโดยใช้ตัวอย่างในภายหลัง ทีนี้มาดูคุณสมบัติภายนอกกัน จากนั้นองค์ประกอบแรกจะเล็กที่สุดและองค์ประกอบสุดท้ายจะใหญ่ที่สุด สิ่งนี้ไม่เป็นความจริงทั้งหมด เพื่อทำความเข้าใจว่าคิวลำดับความสำคัญทำงานอย่างไรและให้อะไร คุณต้องเข้าใจว่าฮีปทำงานอย่างไร เราจะพิจารณาโครงสร้างภายในของลำดับความสำคัญโดยใช้ตัวอย่างในภายหลัง ทีนี้มาดูคุณสมบัติภายนอกกัน
กระบวนการลบเริ่มต้นจากรูท และกระตุ้นให้เกิดกระบวนการย้อนกลับ ดังนั้น อันดับแรกเรามี 1 เป็นรูท จากนั้น 2, 3, 4 และสุดท้ายคือ 5 นั่นเป็นเหตุผลที่ใช้การลบ operation poll()
ประกาศส่วนต่อประสานคิว
public interface Queue<E> extends Collection<E>
คิวลำดับความสำคัญคืออะไร

ตัวสร้างคลาส PriorityQueue และการประกาศ
คลาส PriorityQueue มี 6 วิธีในการสร้างคิวลำดับความสำคัญใน Java- PriorityQueue() - คิวว่างที่มีความจุเริ่มต้นเริ่มต้น (11) ที่เรียงลำดับองค์ประกอบตามลำดับตามธรรมชาติ
- PriorityQueue(Collection c) - คิวว่างที่มีองค์ประกอบในคอลเลกชันที่ระบุ
- PriorityQueue(int initialCapacity) - คิวว่างที่มีความจุเริ่มต้นที่ระบุซึ่งสั่งองค์ประกอบตามลำดับตามธรรมชาติ
- PriorityQueue(int initialCapacity, Comparator comparator) - คิวว่างที่มีความจุเริ่มต้นที่ระบุซึ่งสั่งองค์ประกอบตามตัวเปรียบเทียบที่ระบุ
- PriorityQueue(PriorityQueue c) - คิวว่างที่มีองค์ประกอบในคิวลำดับความสำคัญที่ระบุ
- PriorityQueue(SortSet c) - คิวว่างที่มีองค์ประกอบในชุดเรียงลำดับที่ระบุ
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
การสร้าง PriorityQueue
มาสร้างลำดับความสำคัญของจำนวนเต็มกันเถอะ การใช้งาน Priority Queue, รหัส Java:
PriorityQueue<Integer> numbers = new PriorityQueue<>();
เราได้สร้างคิวลำดับความสำคัญโดยไม่มีข้อโต้แย้ง ในกรณีนี้ ส่วนหัวของคิวลำดับความสำคัญคือจำนวนคิวที่น้อยที่สุด หากคุณถอดหัวออก องค์ประกอบที่เล็กที่สุดถัดไปจะเข้ามาแทนที่ตำแหน่งนี้ คุณจึงสามารถลบองค์ประกอบออกจากคิวตามลำดับจากน้อยไปหามากได้ หากจำเป็น คุณสามารถเปลี่ยนหลักการจัดลำดับโดยใช้อินเทอร์เฟซตัวเปรียบเทียบ
วิธีการ Java PriorityQueue
คลาส PriorityQueue Java มีเมธอดสำคัญในการเพิ่ม ลบ และตรวจสอบอิลิเมนต์แทรกองค์ประกอบลงในคิวลำดับความสำคัญ
- เพิ่มบูลีน (วัตถุ)แทรกองค์ประกอบที่ระบุในคิวลำดับความสำคัญ คืนค่าจริงในกรณีที่สำเร็จ ถ้าคิวเต็ม เมธอดจะส่งข้อยกเว้น
- ข้อเสนอบูลีน (วัตถุ)แทรกองค์ประกอบที่ระบุลงในคิวลำดับความสำคัญนี้ หากคิวเต็ม เมธอดจะส่งกลับค่าเท็จ
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);
}
}
ผลลัพธ์คือ:
[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]
ลำดับขององค์ประกอบดูเหมือนจะแปลก เราจะอธิบายในภายหลัง
การดึงและลบองค์ประกอบออกจาก Priority Queue
- บูลีนลบ (วัตถุ)ลบอินสแตนซ์เดียวขององค์ประกอบที่ระบุออกจากคิวนี้ หากมีอยู่
- การสำรวจวัตถุ ()ดึงและลบส่วนหัวของคิวนี้ คืนค่า null หากคิวว่างเปล่า
- void clear()ลบองค์ประกอบทั้งหมดออกจากลำดับความสำคัญ
- องค์ประกอบวัตถุ ()ดึงส่วนหัวของคิวนี้โดยไม่ต้องลบออก ส่งNoSuchElementExceptionหากคิวว่างเปล่า
- Object peek()ดึงส่วนหัวของคิวโดยไม่ต้องลบออก คืนค่า null หากคิวว่างเปล่า
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());
}
}
ผลลัพธ์:
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)
อย่างที่คุณเห็น การพยายามพิมพ์ส่วนหัวของคิวว่างโดยใช้เมธอด element() นำไปสู่ NoSuchElementexception
PriorityQueue Comparator
- ตัวเปรียบเทียบ ตัวเปรียบเทียบ ()ส่งคืนตัวเปรียบเทียบที่ใช้ในการสั่งซื้อองค์ประกอบในคิว คืนค่า null หากคิวถูกจัดเรียงตามลำดับตามธรรมชาติขององค์ประกอบ
คิวลำดับความสำคัญของ Java ตัวอย่างพร้อมตัวเปรียบเทียบ
เราใช้ลำดับธรรมชาติ (จากน้อยไปหามาก) ในตัวอย่างโค้ดด้านบน แต่บางครั้งเราควรเปลี่ยน นี่คือตัวอย่างคิวลำดับความสำคัญของ Java ที่เราสร้างคลาสตัวเปรียบเทียบภายในของเราเองซึ่งใช้อินเตอร์เฟสตัวเปรียบเทียบ เครื่องมือเปรียบเทียบของเราจะจัดเรียงองค์ประกอบจากใหญ่ไปหาเล็กที่สุด
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;
}
}
}
ผลลัพธ์:
the head of Queue = 5
5
4
3
2
1
ตอนนี้ส่วนหัวของคิวไม่ใช่องค์ประกอบขั้นต่ำ แต่เป็นองค์ประกอบสูงสุด และลำดับถูกเปลี่ยนเป็นกลับด้าน
วนซ้ำ PriorityQueue โดยใช้ตัววนซ้ำ
ProrityQueue เป็นส่วนหนึ่งของเฟรมเวิร์ก Collection และใช้อินเทอร์เฟซIterable<> หากต้องการวนซ้ำองค์ประกอบของคิวลำดับความสำคัญ คุณสามารถใช้เมธอดiterator() นี่คือตัวอย่าง:
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() + " ");
}
}
}
ผลลัพธ์:
1 2 4 5 3
วิธี PriorityQueue เพิ่มเติม
- บูลีนมี (Object o) คืนค่าจริงหากคิวมีองค์ประกอบ o
- int size()ส่งคืนจำนวนองค์ประกอบในคิวนี้
- Object[] toArray()ส่งคืนอาร์เรย์ที่มีองค์ประกอบทั้งหมดในคิวนี้
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);
}
}
}
ผลลัพธ์:
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
นิยาม PriorityQueue Java 8
หากคุณเปิดเอกสารคู่มือ Priorityqueue Java 8 คุณจะพบคำจำกัดความถัดไป:คิวลำดับความสำคัญที่ไม่มีขอบเขตขึ้นอยู่กับฮีปลำดับความสำคัญ องค์ประกอบของคิวลำดับความสำคัญจะเรียงลำดับตามลำดับธรรมชาติ หรือโดยตัวเปรียบเทียบที่จัดไว้ให้ในเวลาสร้างคิว ทั้งนี้ขึ้นอยู่กับตัวสร้างที่ใช้ คิวลำดับความสำคัญไม่อนุญาตให้มีองค์ประกอบที่เป็นค่าว่าง คิวลำดับความสำคัญขึ้นอยู่กับลำดับตามธรรมชาติยังไม่อนุญาตให้แทรกวัตถุที่ไม่สามารถเปรียบเทียบได้ (การทำเช่นนั้นอาจส่งผลให้เกิด ClassCastException) กองเป็นคำที่สำคัญมากที่นี่ โดยจะอธิบายคุณสมบัติของการจัดลำดับองค์ประกอบคิวลำดับความสำคัญหลักการทำงานของ PriorityQueue: Binary Heap
เริ่มจากตัวอย่างกันก่อน มาสร้างวัตถุสองชิ้นที่ใช้ส่วนต่อประสานคิว หนึ่งในนั้น LinkedList รายการที่สอง — PriorityQueue ทั้งคู่มี 5 องค์ประกอบของจำนวนเต็ม (1,2,3,4 และ 5) และเราเริ่มใส่องค์ประกอบลงในคิวของเราจากมากไปน้อย ดังนั้นรายการแรกคือ 5 จากนั้น 4, 3, 2 และรายการสุดท้ายจะเป็น 1 จากนั้นพิมพ์รายการทั้งสองเพื่อตรวจสอบลำดับ
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)
ผลลัพธ์ของการทำงานของโค้ดเหล่านี้คือสิ่งต่อไปนี้:
LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]
ลำดับของรายการที่เชื่อมโยงสามารถคาดเดาได้และเข้าใจได้ สั่งตามหลักการ FIFO เราเริ่มต้นด้วย 5 ดังนั้นองค์ประกอบนี้จึงเป็นองค์ประกอบแรกในบรรทัด จากนั้นจึงไปที่ 4 ไปเรื่อยๆ ลำดับความสำคัญของคิวบอกอะไรเราได้บ้าง? Docs กล่าวว่าองค์ประกอบของคิวลำดับความสำคัญจะเรียงลำดับตามลำดับตามธรรมชาติ หรือโดยตัวเปรียบเทียบที่จัดไว้ให้ในเวลาสร้างคิว อย่างไรก็ตาม คำสั่งนี้ดูเหมือนจะไม่ "เป็นธรรมชาติ" ในความหมายการเรียงลำดับเชิงเส้น เราค่อนข้างคาดหวัง [1, 2, 3, 4, 5] ไม่ใช่ [1, 2, 4, 5, 3] เพื่อทำความเข้าใจว่าเหตุใดลำดับของการดึงข้อมูลจึงเป็นเช่นนี้ เราควรเรียกคืนลำดับความสำคัญตามฮีป กองคืออะไร? เป็นโครงสร้างข้อมูลแบบไบนารี่ทรี. คุณสมบัติหลักของฮีป: ลำดับความสำคัญของพาเรนต์แต่ละตัวนั้นมากกว่าลำดับความสำคัญของลูก ฉันขอเตือนคุณว่าต้นไม้เรียกว่าไบนารีที่สมบูรณ์หากผู้ปกครองแต่ละคนมีลูกไม่เกินสองคน และการเติมระดับจะเรียงจากบนลงล่าง (จากระดับเดียวกัน — จากซ้ายไปขวา) ฮีปไบนารีจัดระเบียบตัวเองใหม่ทุกครั้งที่มีการเพิ่มหรือลบองค์ประกอบออกจากฮีป ในกรณีของ min-heap องค์ประกอบที่เล็กที่สุดจะไปที่รูทโดยไม่คำนึงถึงลำดับของการแทรก ลำดับความสำคัญตาม min-heap นี้ นั่นหมายความว่า ในกรณีขององค์ประกอบคิวที่เป็นตัวเลข องค์ประกอบแรกของคิวจะเป็นจำนวนที่น้อยที่สุด หากคุณลบรูท ตัวที่เล็กที่สุดตัวถัดไปจะกลายเป็นรูท
มาดูตัวอย่างของเรากัน
ขั้นตอนที่ 1เราใส่ '5' ลงในคิวลำดับความสำคัญ มันจะกลายเป็นราก ขั้นตอนที่ 2เราเพิ่ม '4' ในคิวลำดับความสำคัญ 4 <5 ดังนั้นองค์ประกอบใหม่ควรสูงกว่าองค์ประกอบเก่า 4 กลายเป็นราก 5 เป็นลูกซ้าย ตอนนี้โครงสร้างข้อมูลใน Java คือ [4, 5] ขั้นตอนที่ 3เราเพิ่ม '3' มันจะกลายเป็นลูกที่ถูกต้องของรากชั่วคราว (4) อย่างไรก็ตาม 3 < 4 ดังนั้นเราควรยกมันขึ้น แลกเปลี่ยน 3 และ 4 ตอนนี้เรามีโครงสร้างเช่น [3, 5, 4] ขั้นตอนที่ 4เราเพิ่ม '2' มันกลายเป็นลูกที่เหลือของ 5 2<5 ดังนั้นแลกเปลี่ยนกัน 2 กลายเป็นลูกที่เหลือของ 3, 2 < 3, ดังนั้นอีกหนึ่งกระบวนการแลกเปลี่ยน. ตอนนี้เรามีโครงสร้าง [2,3,4,5] ขั้นตอนที่ 5เราเพิ่ม '1' มันมาจากลูกด้านขวาของ 3 ไปยังลูกด้านซ้ายของ 2 แล้วไปที่ราก โครงสร้างข้อมูลผลลัพธ์: [1,2,4,5,3]
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
เราได้ "เรียงลำดับ" ในเอาต์พุตเชิงเส้น:
1
2
3
4
5
คิวลำดับความสำคัญจึงอาจมีผลกับการดำเนินการบางอย่าง ใช้เวลา O(log N) ในการแทรกและลบแต่ละองค์ประกอบ และคุณจะได้องค์ประกอบขั้นต่ำใน O(1) นี่คือตัวอย่างแบบเต็ม:
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
สิ่งสำคัญคือต้องเข้าใจว่าคิวลำดับความสำคัญขึ้นอยู่กับฮีปแบบไบนารี ดังนั้นจึงไม่เก็บองค์ประกอบตามลำดับการเรียงเชิงเส้น ทุกวิถีทางจากรากถึงใบถูกสั่ง แต่วิธีที่แตกต่างจากรากนั้นไม่ได้ นั่นหมายความว่าคุณจะได้รับองค์ประกอบขั้นต่ำของคิวอย่างรวดเร็ว
สิ่งที่คุณควรทราบเกี่ยวกับคิวลำดับความสำคัญ รายการสั้น ๆ
- Priority Queue ไม่อนุญาตให้ใช้วัตถุ NULL
- คุณสามารถเพิ่มวัตถุที่เทียบเคียงได้ใน PriorityQueue เท่านั้น
- คิวลำดับความสำคัญถูกสร้างขึ้นเป็น min heap ซึ่งเป็นต้นไม้ไบนารีชนิดหนึ่ง องค์ประกอบขั้นต่ำคือราก ออบเจกต์ของคิวลำดับความสำคัญจะเรียงลำดับตามค่าเริ่มต้นในลำดับปกติ
- คุณสามารถใช้ตัวเปรียบเทียบหากคุณต้องการสั่งซื้อแบบกำหนดเอง
- PriorityQueue ไม่ปลอดภัยสำหรับเธรด ดังนั้นคุณควรใช้ PriorityBlockingQueue เพื่อทำงานในสภาพแวดล้อมพร้อมกัน
- PriorityQueue ให้เวลา O(log(n)) สำหรับวิธีการเพิ่มและสำรวจความคิดเห็น และ O(1) เพื่อรับองค์ประกอบขั้นต่ำ
GO TO FULL VERSION