Οι ουρές προτεραιότητας στην Java εξηγούνται με παραδείγματα

Οι ουρές προτεραιότητας χρησιμοποιούνται πολύ συχνά σε εφαρμογές πραγματικής ζωής. Σε αυτό το άρθρο θα μάθουμε τι είναι οι ουρές προτεραιότητας και πώς μπορούμε να τις χρησιμοποιήσουμε στην 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()

Το poll () θα μας δώσει το πιο πρόσφατο στοιχείο και θα το αφαιρέσουμε επίσης από την ουρά. Εάν θέλουμε να λάβουμε το πιο πρόσφατο στοιχείο στην ουρά χωρίς να το αφαιρέσουμε, μπορούμε να χρησιμοποιήσουμε τη λειτουργία peek () :

testStringsPQ.peek()

Τέλος, εκτυπώνουμε όλα τα στοιχεία από την ουρά χρησιμοποιώντας τη συνάρτηση poll () όπως φαίνεται παρακάτω:

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.

Let's first create a class called CustomerOrder which is used to store customer order details:

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

This is a simple Java class to store customer orders. This class implements comparable interface, so that we can decide on what basis this object needs to be ordered in the priority queue.

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

Λατρεύω την τεχνολογία και παρακολουθώ τις εξελίξεις στον τομέα. Μου αρέσει επίσης να βοηθάω άλλους με τις τεχνολογικές μου γνώσεις.

Μη διστάσετε να συνδεθείτε μαζί μου στο λογαριασμό μου στο LinkedIn //www.linkedin.com/in/aditya1811/

Μπορείτε επίσης να με ακολουθήσετε στο twitter //twitter.com/adityasridhar18

Μη διστάσετε να διαβάσετε περισσότερα από τα άρθρα μου στο blog μου στο adityasridhar.com.