java priority queue tutorial implementation examples
Αυτό το σεμινάριο εξηγεί την ουρά προτεραιότητας Java και σχετικές έννοιες όπως το Comparator, Min και Max Priority Queue μαζί με την εφαρμογή του με παραδείγματα:
Η δομή δεδομένων ουράς προτεραιότητας είναι μια ειδική ουρά στην οποία τα στοιχεία υπάρχουν όχι σύμφωνα με τη σειρά FIFO αλλά σύμφωνα με τα φυσικά στοιχεία ή οποιοδήποτε προσαρμοσμένο συγκριτικό που χρησιμοποιείται κατά τη δημιουργία της ουράς.
=> Ρίξτε μια ματιά στον οδηγό για αρχάριους Java εδώ.
Τι θα μάθετε:
Ουρά προτεραιότητας στην Java
Στην ουρά προτεραιότητας, το μπροστινό μέρος της ουράς έχει τα λιγότερα στοιχεία σύμφωνα με τη φυσική σειρά και το πίσω μέρος είναι στραμμένο προς το μεγαλύτερο στοιχείο στην ουρά.
Ένα παράδειγμα ουράς προτεραιότητας που αποτελείται από αριθμούς φαίνεται παρακάτω.
δωρεάν χάρτης ροής για mac
Έτσι, όταν ένα στοιχείο αφαιρείται από την ουρά προτεραιότητας που φαίνεται παραπάνω, τότε θα είναι το λιγότερο στοιχείο.
Ομοίως, για μια αλφαβητική ουρά προτεραιότητας, θα ληφθούν υπόψη οι τιμές ASCII και τα στοιχεία ουράς θα ταξινομηθούν σύμφωνα με τις τιμές ASCII.
Παρακάτω αναφέρονται μερικά από τα κύρια χαρακτηριστικά του PriorityQueue:
- Το PriorityQueue είναι μια απεριόριστη ουρά.
- Το PriorityQueue δεν επιτρέπει μηδενικές τιμές.
- Για μη συγκρίσιμα αντικείμενα, δεν μπορούμε να δημιουργήσουμε ουρά προτεραιότητας.
- Το PriorityQueue κληρονομεί από τις τάξεις όπως AbstractQueue, AbstractCollection, Collection και Object.
- Το κεφάλι ή το μπροστινό μέρος της ουράς περιέχει το λιγότερο στοιχείο σύμφωνα με τη φυσική σειρά.
- Η εφαρμογή ουράς προτεραιότητας δεν είναι ασφαλής για θέματα. Επομένως, εάν θέλουμε συγχρονισμένη πρόσβαση, θα πρέπει να χρησιμοποιήσουμε το PriorityBlockingQueue.
Η κλάση PriorityQueue κληρονομεί το Java Queue Interface και αποτελεί μέρος του πακέτου java.util.
Η γενική δήλωση της κατηγορίας PriorityQueue δίνεται παρακάτω:
public class PriorityQueue extends AbstractQueue implements SerializableΤο παρακάτω διάγραμμα δείχνει την ιεραρχία κλάσης για την κατηγορία PriorityQueue.
Χρόνος πολυπλοκότητας της ουράς προτεραιότητας
- Η χρονική πολυπλοκότητα της ουράς προτεραιότητας για τις μεθόδους εισαγωγής (enqueue) και διαγραφής (dequeue), είναι O (log (n)).
- Η ουρά προτεραιότητας έχει γραμμική πολυπλοκότητα χρόνου για κατάργηση καθώς και μεθόδους.
- Οι μέθοδοι που ανακτούν στοιχεία της ουράς προτεραιότητας έχουν συνεχή πολυπλοκότητα χρόνου.
Παράδειγμα ουράς προτεραιότητας στην Java
Το παρακάτω πρόγραμμα δείχνει ένα απλό PriorityQueue στην Java. Δημιουργούμε ένα αντικείμενο κλάσης PriorityQueue, προσθέτουμε τιμές σε αυτό και, στη συνέχεια, εμφανίζουμε τα περιεχόμενα της ουράς χρησιμοποιώντας το Iterator.
import java.util.*; class Main{ public static void main(String args()){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } Παραγωγή:
Μέθοδοι API ουράς προτεραιότητας Java
Κατασκευαστές:
| Πρωτότυπο κατασκευαστή | Περιγραφή | |
|---|---|---|
| κρυφοκοίταγμα | E peek () | Επιστρέφει την κεφαλή της ουράς χωρίς να διαγράψει το στοιχείο. |
| ΠροτεραιότηταQueue () | Ένας προεπιλεγμένος κατασκευαστής που δημιουργεί ένα αντικείμενο PriorityQueue με αρχική χωρητικότητα ως 1. | |
| PriorityQueue (Συλλογή γ) | Δημιουργεί ένα αντικείμενο PriorityQueue με αρχικά στοιχεία από μια δεδομένη συλλογή c. | |
| PriorityQueue (intitialCapacity) | Δημιουργεί ένα αντικείμενο PriorityQueue με το δεδομένο 'initialCapacity'. Τα στοιχεία ταξινομούνται σύμφωνα με τη φυσική σειρά. | |
| PriorityQueue (intitialCapacity, Συγκριτικός συγκριτής) | Δημιουργεί ένα αντικείμενο PriorityQueue με το δεδομένο 'initialCapacity'. Τα στοιχεία ταξινομούνται σύμφωνα με τον δεδομένο συγκριτή. | |
| PriorityQueue (PriorityQueue γ) | Δημιουργεί ένα αντικείμενο PriorityQueue από άλλο αντικείμενο PriorityQueue που δίνεται από το c. | |
| PriorityQueue (ΤαξινόμησηSet c) | Δημιουργεί ένα αντικείμενο PriorityQueue από ένα SortedSet που δίνεται από το c. |
Μέθοδοι
| Μέθοδος | Πρωτότυπο μεθόδου | Περιγραφή |
|---|---|---|
| Προσθήκη | boolean add (E ε) | Προσθέτει το στοιχείο e στο PriorityQueue. |
| Σαφή | κενό καθαρό () | Διαγράφει το PriorityQueue διαγράφοντας όλα τα στοιχεία. |
| συγκριτής | Συγκριτής | Επιστρέφει ένα προσαρμοσμένο συγκριτικό που χρησιμοποιείται για τη σειρά των στοιχείων στην ουρά. |
| περιέχει | Το boolean περιέχει (αντικείμενο o) | Ελέγχει εάν το PriorityQueue περιέχει το δεδομένο στοιχείο o. Επιστρέφει true αν ναι. |
| επαναληπτικό | Επαναληπτικός () | Μέθοδος για να λάβετε έναν επαναληπτικό για το δεδομένο PriorityQueue. |
| προσφορά | boolean προσφορά (E ε) | Εισαγωγή δεδομένου στοιχείου e στο PriorityQueue. |
| ψηφοφορία | E δημοσκόπηση () | Αφαιρεί και επιστρέφει την κεφαλή της ουράς. Επιστρέφει null εάν η ουρά είναι κενή. |
| αφαιρώ | boolean remove (Αντικείμενο o) | Καταργεί μια παρουσία ενός δεδομένου στοιχείου o εάν υπάρχει στην ουρά. |
| Μέγεθος | int μέγεθος () | Επιστρέφει το μέγεθος ή τον αριθμό των στοιχείων σε αυτό το PriorityQueue. |
| στο Array | Αντικείμενο () toArray () | Επιστρέφει μια παράσταση πίνακα του δεδομένου PriorityQueue. |
| στο Array | T () toArray (T () α) | Επιστρέφει μια αναπαράσταση πίνακα για τη δεδομένη ουρά προτεραιότητας με τον ίδιο τύπο χρόνου εκτέλεσης με τον καθορισμένο πίνακα α. |
Υλοποίηση σε Java
Ας δείξουμε τις παραπάνω μεθόδους του PriorityQueue χρησιμοποιώντας ένα πρόγραμμα Java.
import java.util.*; class Main { public static void main(String args()) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object() numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i Παραγωγή:
τι μπορεί να ανοίξει ένα αρχείο json
Ουρά προτεραιότητας στην Java 8
Το Java 8 προσθέτει μια ακόμη μέθοδο στην κατηγορία PriorityQueue, δηλαδή «spliterator ()».
Οι λεπτομέρειες αυτής της μεθόδου δίνονται παρακάτω.
Όνομα μεθόδου: σχίστης
Πρωτότυπο μεθόδου: δημόσιο τελικό Spliterator spliterator ()
Περιγραφή μεθόδου: Αυτή η μέθοδος δημιουργεί έναν διαχωριστή πάνω από τα στοιχεία PriorityQueue. Αυτός ο διαχωριστής είναι αργά δεσμευτικός και γρήγορος.
Συγκριτής ουράς προτεραιότητας
Όπως προαναφέρθηκε, τα στοιχεία PriorityQueue είναι φυσικά ταξινομημένα. Εάν θέλουμε να αλλάξουμε τη σειρά, τότε πρέπει να καθορίσουμε ένα συγκριτικό και να το χρησιμοποιήσουμε κατά τη δημιουργία του αντικειμένου PriorityQueue. Στη συνέχεια, το PriorityQueue χρησιμοποιεί αυτόν τον συγκριτή για να ταξινομήσει τα στοιχεία του.
Το παρακάτω πρόγραμμα Java δείχνει τη χρήση προσαρμοσμένου συγκριτή για την παραγγελία στοιχείων. Σε αυτό το πρόγραμμα, ορίζουμε έναν νέο προσαρμοσμένο συγκριτή μέσα στον οποίο παρακάμπτουμε τη μέθοδο «σύγκριση». Η μέθοδος σύγκρισης χρησιμοποιείται για την παραγγελία των στοιχείων του PriorityQueue ανάλογα με το μήκος.
import java.util.*; public class Main { public static void main(String() args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } Παραγωγή:
Ελάχιστη ουρά προτεραιότητας στην Ιάβα
Η φυσική σειρά της σειράς προτεραιότητας έχει το μικρότερο ή μικρότερο στοιχείο στην κεφαλή της ουράς και έτσι η σειρά αυξάνεται. Αυτό ονομάζεται «ουρά ελάχιστης προτεραιότητας» με αύξουσα σειρά στοιχείων.
Το παρακάτω πρόγραμμα Java δείχνει την υλοποίηση του Min Priority Queue στην Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } Παραγωγή:
ευέλικτες ερωτήσεις συνέντευξης και απαντήσεις για έμπειρους
Μέγιστη ουρά προτεραιότητας στην Java
Ενώ η ουρά ελάχιστης προτεραιότητας έχει στοιχεία σε αύξουσα σειρά, η ουρά μέγιστης προτεραιότητας έχει τα στοιχεία σε φθίνουσα σειρά, δηλ. Η κεφαλή της ουράς μέγιστης προτεραιότητας θα επιστρέψει το μεγαλύτερο στοιχείο στην ουρά.
Το παρακάτω πρόγραμμα Java δείχνει το Max Priority Queue στην Java.
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs Παραγωγή:
Όπως φαίνεται στο παραπάνω πρόγραμμα, για να αλλάξουμε τη φυσική σειρά των στοιχείων στην ουρά προτεραιότητας, πρέπει να ορίσουμε έναν προσαρμοσμένο συγκριτή.
Συχνές Ερωτήσεις
Q # 1) Ποια είναι η ουρά προτεραιότητας στην Java;
Απάντηση: Μια ειδική ουρά στην οποία όλα τα στοιχεία της ουράς ταξινομούνται σύμφωνα με τη φυσική παραγγελία ή χρησιμοποιώντας ένα προσαρμοσμένο συγκριτή ονομάζεται ουρά προτεραιότητας. Δεν ακολουθεί την παραγγελία FIFO.
Q # 2) Πώς μπορείτε να ορίσετε μια ουρά Max Priority στην Java;
Απάντηση: Μπορούμε να ορίσουμε μια ουρά μέγιστης προτεραιότητας στην Java χρησιμοποιώντας ένα προσαρμοσμένο συγκριτικό έτσι ώστε ο επικεφαλής της ουράς να επιστρέψει το μεγαλύτερο στοιχείο στην ουρά.
Ε # 3) Η ουρά προτεραιότητας επιτρέπει διπλότυπα Java;
Απάντηση: Ναί. Η ουρά προτεραιότητας επιτρέπει διπλές τιμές.
Q # 4) Είναι η ουρά Java Priority max ή min;
Απάντηση: Από προεπιλογή, η ουρά προτεραιότητας στη Java είναι ελάχιστη ουρά προτεραιότητας με φυσική σειρά. Για να το κάνουμε μέγιστο, πρέπει να χρησιμοποιήσουμε ένα προσαρμοσμένο συγκριτικό έτσι ώστε η κεφαλή της ουράς να επιστρέψει το μεγαλύτερο στοιχείο στην ουρά.
Ε # 5) Έχει ταξινομηθεί μια ουρά προτεραιότητας;
Απάντηση: Από προεπιλογή, η κεφαλή της ουράς ταξινομείται και η ουρά προτεραιότητας έχει το λιγότερο στοιχείο ως κεφαλή. Τα υπόλοιπα στοιχεία ταξινομούνται όταν απαιτείται.
συμπέρασμα
Αυτό ολοκληρώνει το σεμινάριο για τις ουρές προτεραιότητας στην Java. Το Priority Queue εφαρμόζει μια διεπαφή ουράς και είναι μια ειδική ουρά όπου τα στοιχεία ταξινομούνται σύμφωνα με τη φυσική σειρά. Δεν ακολουθεί την παραγγελία FIFO. Για να αλλάξουμε τη φυσική σειρά της ουράς προτεραιότητας, μπορούμε να χρησιμοποιήσουμε το προσαρμοσμένο συγκριτικό.
Οι ουρές προτεραιότητας χρησιμοποιούνται κυρίως για τον προγραμματισμό εκτυπωτή, τον προγραμματισμό εργασιών CPU κ.λπ. Ο σωρός (ελάχιστο ή μέγιστο) εφαρμόζεται επίσης χρησιμοποιώντας ουρές προτεραιότητας.
=> Διαβάστε ολόκληρη τη σειρά Easy Java Training.
Συνιστώμενη ανάγνωση
- Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση
- Ουρά προτεραιότητας στο STL
- Java Queue - Μέθοδοι ουράς, υλοποίηση ουράς με παραδείγματα
- Δομή δεδομένων κυκλικής ουράς C ++: Εφαρμογή & εφαρμογές
- Διπλή ουρά (Deque) σε C ++ με παραδείγματα
- Δομή δεδομένων ουράς σε C ++ με απεικόνιση
- Στοίβες και ουρές στο STL
- Εκπαιδευτικό πρόγραμμα JAVA για αρχάριους: 100+ πρακτικά εκπαιδευτικά βίντεο Java
