ลำดับความสำคัญใน Java อธิบายด้วยตัวอย่าง

Priority Queues ใช้บ่อยมากในการใช้งานจริง ในบทความนี้เราจะเรียนรู้ว่าคิวลำดับความสำคัญคืออะไรและเราจะใช้มันใน Java ได้อย่างไร

ก่อนที่เราจะคุยกันว่าลำดับความสำคัญคืออะไรมาดูกันว่าคิวปกติคืออะไร

คิวปกติเป็นไปตามโครงสร้างก่อนออกก่อน (FIFO) ซึ่งหมายความว่าถ้า 3 ข้อความ - m1, m2 และ m3 - เข้าไปในคิวตามลำดับนั้นก็จะออกมาจากคิวในลำดับเดียวกัน

ทำไมเราต้องรอคิว?

สมมติว่าเรามีผู้ผลิตข้อมูล (ตัวอย่างเช่นเมื่อผู้ใช้คลิกบนหน้าเว็บ) ซึ่งเร็วมาก แต่เราต้องการใช้ข้อมูลนี้ในอัตราที่ช้าลงในภายหลัง

ในกรณีนี้ผู้ผลิตจะพุชข้อความทั้งหมดลงในคิวและผู้บริโภคจะใช้ข้อความเหล่านี้ในภายหลังจากคิวในจังหวะที่ช้าลง

ลำดับความสำคัญคืออะไร?

ดังที่ได้กล่าวไว้ก่อนหน้านี้คิวปกติมีโครงสร้างก่อนเข้าก่อน แต่ในบางสถานการณ์เราต้องการประมวลผลข้อความในคิวตามลำดับความสำคัญและไม่อิงตามเวลาที่ข้อความเข้าสู่คิว

คิวลำดับความสำคัญช่วยให้ผู้บริโภคใช้ข้อความที่มีลำดับความสำคัญสูงกว่าก่อนตามด้วยข้อความที่มีลำดับความสำคัญต่ำกว่า

ลำดับความสำคัญของคิวใน Java

ตอนนี้เรามาดูโค้ด Java จริงที่จะแสดงวิธีใช้คิวลำดับความสำคัญ

จัดลำดับความสำคัญด้วยลำดับตามธรรมชาติ

นี่คือโค้ดบางส่วนที่แสดงวิธีสร้างคิวลำดับความสำคัญอย่างง่ายสำหรับสตริง

private static void testStringsNaturalOrdering() { Queue testStringsPQ = new PriorityQueue(); testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy"); System.out.println("Strings Stored in Natural Ordering in a Priority Queue\n"); while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); } }

บรรทัดแรกบอกเราว่าเรากำลังสร้างลำดับความสำคัญ:

Queue testStringsPQ = new PriorityQueue();

PriorityQueue มีอยู่ในแพ็คเกจ java.util

ต่อไปเราจะเพิ่ม 5 สตริงในลำดับความสำคัญแบบสุ่ม สำหรับสิ่งนี้เราใช้ฟังก์ชันadd ()ดังที่แสดงด้านล่าง:

testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy");

ในการรับรายการล่าสุดจากคิวเราใช้ฟังก์ชันPoll ()ดังที่แสดงด้านล่าง:

testStringsPQ.poll()

การสำรวจความคิดเห็น ()จะให้รายการล่าสุดแก่เราและลบออกจากคิวด้วย หากเราต้องการรับรายการล่าสุดในคิวโดยไม่ต้องลบออกเราสามารถใช้ฟังก์ชันpeek () :

testStringsPQ.peek()

สุดท้ายเราพิมพ์องค์ประกอบทั้งหมดจากคิวโดยใช้ฟังก์ชันโพล () ดังที่แสดงด้านล่าง:

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

นี่คือผลลัพธ์ของโปรแกรมข้างต้น:

1234 23bc abcd abxy zzxx

เนื่องจากเราไม่ได้บอกลำดับความสำคัญว่าจะจัดลำดับความสำคัญของเนื้อหาอย่างไรจึงใช้ลำดับความสำคัญเริ่มต้น ในกรณีนี้จะให้ข้อมูลย้อนกลับในลำดับสตริงจากน้อยไปหามาก นี่ไม่ใช่ลำดับเดียวกับที่เพิ่มรายการลงในคิว

สิ่งที่เกี่ยวกับการสั่งซื้อที่กำหนดเอง?

สิ่งนี้เป็นไปได้เช่นกันและเราสามารถทำได้ด้วยความช่วยเหลือของตัวเปรียบเทียบ

มาสร้างคิวลำดับความสำคัญจำนวนเต็มทันที แต่คราวนี้ให้ผลลัพธ์เป็นค่าจากมากไปหาน้อย

เพื่อให้บรรลุสิ่งนี้ก่อนอื่นเราต้องสร้างตัวเปรียบเทียบจำนวนเต็ม:

 static class CustomIntegerComparator implements Comparator { @Override public int compare(Integer o1, Integer o2) { return o1 < o2 ? 1 : -1; } }

ในการสร้างตัวเปรียบเทียบเราใช้อินเทอร์เฟซตัวเปรียบเทียบและแทนที่วิธีการเปรียบเทียบ

โดยใช้o1 <o2? 1: -1เราจะได้ผลลัพธ์จากมากไปหาน้อย ถ้าเราเคยใช้o1> o2? 1: -1เราจะได้ผลลัพธ์จากน้อยไปมาก

ตอนนี้เรามีตัวเปรียบเทียบแล้วเราต้องเพิ่มตัวเปรียบเทียบนี้ในคิวลำดับความสำคัญ เราสามารถทำได้ดังนี้:

Queue testIntegersPQ = new PriorityQueue(new CustomIntegerComparator());

นี่คือส่วนที่เหลือของโค้ดที่เพิ่มองค์ประกอบลงในคิวลำดับความสำคัญและพิมพ์ออกมา:

 testIntegersPQ.add(11); testIntegersPQ.add(5); testIntegersPQ.add(-1); testIntegersPQ.add(12); testIntegersPQ.add(6); System.out.println("Integers stored in reverse order of priority in a Priority Queue\n"); while (!testIntegersPQ.isEmpty()) { System.out.println(testIntegersPQ.poll()); }

ผลลัพธ์ของโปรแกรมข้างต้นแสดงไว้ด้านล่าง:

12 11 6 5 -1

เราจะเห็นว่าตัวเปรียบเทียบทำงานได้ดี ตอนนี้ลำดับความสำคัญคือให้เราได้จำนวนเต็มตามลำดับจากมากไปหาน้อย

ลำดับความสำคัญของคิวกับวัตถุ Java

จนถึงจุดนี้เราได้เห็นว่าเราสามารถใช้สตริงและจำนวนเต็มกับคิวลำดับความสำคัญได้อย่างไร

ในชีวิตจริงโดยทั่วไปเราจะใช้ลำดับความสำคัญคิวกับวัตถุ Java ที่กำหนดเอง

ก่อนอื่นเรามาสร้างคลาสชื่อว่า CustomerOrder ซึ่งใช้ในการจัดเก็บรายละเอียดการสั่งซื้อของลูกค้า:

public class CustomerOrder implements Comparable { private int orderId; private double orderAmount; private String customerName; public CustomerOrder(int orderId, double orderAmount, String customerName) { this.orderId = orderId; this.orderAmount = orderAmount; this.customerName = customerName; } @Override public int compareTo(CustomerOrder o) { return o.orderId > this.orderId ? 1 : -1; } @Override public String toString() { return "orderId:" + this.orderId + ", orderAmount:" + this.orderAmount + ", customerName:" + customerName; } public double getOrderAmount() { return orderAmount; } }

นี่คือคลาส Java ง่ายๆในการจัดเก็บคำสั่งซื้อของลูกค้า คลาสนี้ใช้อินเทอร์เฟซที่เทียบเคียงได้เพื่อให้เราสามารถตัดสินใจได้ว่าจะต้องเรียงลำดับวัตถุนี้ในลำดับความสำคัญใด

The ordering is decided by the compareTo function in the above code. The line o.orderId > this.orderId ? 1 : -1 instructs that the orders should be sorted based on descending order of the orderId field

Below is the code which creates a priority queue for the CustomerOrder object:

CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code three customer orders have been created and added to the priority queue.

When we run this code we get the following output:

orderId:3, orderAmount:50.0, customerName:customer3 orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1

As expected, the result comes in descending order of the orderId.

What if we want to prioritize based on orderAmount?

This is again a real life scenario. Let's say that by default the CustomerOrder object is prioritized by the orderId. But then we need a way in which we can prioritize based on orderAmount.

You may immediately think that we can modify the compareTo function in the CustomerOrder class to order based on orderAmount.

But the CustomerOrder class may be used in multiple places in the application, and it would interfere with the rest of the application if we modify the compareTo function directly.

The solution to this is pretty simple: we can create a new custom comparator for the CustomerOrder class and use that along with the priority queue

Below is the code for the custom comparator:

 static class CustomerOrderComparator implements Comparator { @Override public int compare(CustomerOrder o1, CustomerOrder o2) { return o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; } }

This is very similar to the custom integer comparator we saw earlier.

The line o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; indicates that we need to prioritize based on descending order of orderAmount.

Below is the code which creates the priority queue:

 CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(new CustomerOrderComparator()); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code we are passing the comparator to the priority queue in the following line of code:

Queue customerOrders = new PriorityQueue(new CustomerOrderComparator());

Below is the result when we run this code:

orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1 orderId:3, orderAmount:50.0, customerName:customer3

We can see that the data comes in descending order of the orderAmount.

Code

All the code discussed in this article can be found in this GitHub repo.

Congrats ?

You now know how to use priority queues in Java.

About the author

I love technology and follow the advancements in the field. I also like helping others with my technology knowledge.

Feel free to connect with me on my LinkedIn account //www.linkedin.com/in/aditya1811/

You can also follow me on twitter //twitter.com/adityasridhar18

Feel free to read more of my articles on my blog at adityasridhar.com.