Μενού

Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση

  • Κύριος
  • Αλλα
  • Δομή δεδομένων ουράς προτεραιότητας σε C ++ με απεικόνιση

priority queue data structure c with illustration

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Εισαγωγή στην ουρά προτεραιότητας στο C ++ με απεικόνιση.

Το Priority Queue είναι μια επέκταση της ουράς που συζητήσαμε στο τελευταίο μας σεμινάριο.

Είναι παρόμοιο με την ουρά σε ορισμένες πτυχές, αλλά διαφέρει από την συνηθισμένη ουρά στα ακόλουθα σημεία:

  • Κάθε στοιχείο στην ουρά προτεραιότητας σχετίζεται με προτεραιότητα.
  • Το στοιχείο με την υψηλότερη προτεραιότητα είναι το πρώτο στοιχείο που πρέπει να αφαιρεθεί από την ουρά.
  • Εάν περισσότερα από ένα στοιχεία έχουν την ίδια προτεραιότητα, τότε λαμβάνεται υπόψη η σειρά τους στην ουρά.

=> Κάντε κλικ εδώ για την σειρά απόλυτης προπόνησης C ++.

Ουρά προτεραιότητας σε C ++

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

Τι θα μάθετε:

Βασικές λειτουργίες

Ας συζητήσουμε μερικές από τις βασικές λειτουργίες που υποστηρίζονται από την ουρά προτεραιότητας.

  • Εισαγωγή (στοιχείο, προτεραιότητα): Εισάγει ένα στοιχείο στην ουρά προτεραιότητας με δεδομένη προτεραιότητα.
  • getHighestPriority (): Επιστρέφει ένα στοιχείο με την υψηλότερη προτεραιότητα.
  • deleteHighestPriority (): Καταργεί ένα στοιχείο με την υψηλότερη προτεραιότητα.

Εκτός από τις παραπάνω λειτουργίες, μπορούμε επίσης να χρησιμοποιήσουμε τις κανονικές λειτουργίες ουράς όπως isEmpty (), isFull () και peek ().

Απεικόνιση

Ας δούμε μια εικόνα της ουράς προτεραιότητας. Για λόγους απλότητας, θα χρησιμοποιήσουμε χαρακτήρες ASCII ως στοιχεία στην ουρά προτεραιότητας. Όσο υψηλότερη είναι η τιμή ASCII, τόσο υψηλότερη είναι η προτεραιότητα.

Αρχική κατάσταση - Ουρά προτεραιότητας (PQ) - {} => κενό

απεικόνιση της ουράς προτεραιότητας

Από την παραπάνω εικόνα, βλέπουμε ότι η λειτουργία εισαγωγής είναι παρόμοια με μια συνηθισμένη ουρά. Αλλά όταν ονομάζουμε 'deleteHighestPriority' για την ουρά προτεραιότητας, το στοιχείο με την υψηλότερη προτεραιότητα καταργείται πρώτα.

Ως εκ τούτου, την πρώτη φορά που καλούμε αυτήν τη συνάρτηση, το στοιχείο O αφαιρείται ενώ τη δεύτερη φορά, το στοιχείο M αφαιρείται καθώς έχει υψηλότερη προτεραιότητα από τα G και A.

Εφαρμογή ουρών προτεραιότητας στο C ++

Οι ουρές προτεραιότητας μπορούν να εφαρμοστούν χρησιμοποιώντας:

# 1) Πίνακες / Συνδεδεμένες λίστες

Μπορούμε να εφαρμόσουμε τις ουρές προτεραιότητας χρησιμοποιώντας πίνακες και αυτή είναι η απλούστερη εφαρμογή για τις ουρές προτεραιότητας.

Για να αντιπροσωπεύσουμε τα στοιχεία στην ουρά προτεραιότητας, μπορούμε απλώς να δηλώσουμε μια δομή όπως παρακάτω:

struct pq_item{ int item; int priority; };

Έχουμε δηλώσει επίσης την προτεραιότητα για κάθε στοιχείο.

Για να εισαγάγετε ένα νέο στοιχείο στην ουρά προτεραιότητας, απλά πρέπει να εισαγάγετε το στοιχείο στο τέλος του πίνακα.

Για να λάβουμε το στοιχείο από την ουρά χρησιμοποιώντας το getHighestPriority (), πρέπει να διασχίσουμε τον πίνακα από την αρχή και να επιστρέψουμε το στοιχείο με την υψηλότερη προτεραιότητα.

Ομοίως, για να αφαιρέσουμε το στοιχείο από την ουρά χρησιμοποιώντας τη λειτουργία deleteHighestPriority, πρέπει να διασχίσουμε ολόκληρο τον πίνακα και να διαγράψουμε το στοιχείο με την υψηλότερη προτεραιότητα. Στη συνέχεια, μετακινήστε όλα τα άλλα στοιχεία μετά το διαγραμμένο στοιχείο, μία θέση πίσω.

Μπορούμε επίσης να εφαρμόσουμε την ουρά προτεραιότητας χρησιμοποιώντας μια συνδεδεμένη λίστα. Μπορούμε να εκτελέσουμε όλες τις λειτουργίες με παρόμοιο τρόπο όπως πίνακες. Η μόνη διαφορά είναι ότι δεν χρειάζεται να μετακινήσουμε τα στοιχεία αφού καλέσουμε το deleteHighestPriority.

# 2) Σωρούς

Η χρήση σωρών για την εφαρμογή ουράς προτεραιότητας είναι ο πιο αποτελεσματικός τρόπος και παρέχει πολύ καλύτερη απόδοση σε σύγκριση με τις συνδεδεμένες λίστες και πίνακες. Σε αντίθεση με τη συνδεδεμένη λίστα και πίνακα, η εφαρμογή σωρού απαιτεί O (logn) χρόνο για εισαγωγή και διαγραφή λειτουργιών της ουράς προτεραιότητας. Λάβετε λειτουργία, το getHighestPriority διαρκεί O (1) χρόνος.

# 3) Ενσωματωμένη ουρά προτεραιότητας σε τυπική βιβλιοθήκη προτύπων (STL) σε C ++

Στο C ++, έχουμε μια ουρά προτεραιότητας ως προσαρμοσμένη κλάση κοντέινερ, σχεδιασμένη με τέτοιο τρόπο ώστε το υψηλότερο στοιχείο να είναι το πρώτο στοιχείο στην ουρά και όλα τα στοιχεία να είναι σε φθίνουσα σειρά.

Έτσι, κάθε στοιχείο στην ουρά προτεραιότητας έχει σταθερή προτεραιότητα.

Έχουμε τάξη στο STL, το οποίο περιέχει την εφαρμογή ουράς προτεραιότητας.

Οι διάφορες λειτουργίες που υποστηρίζονται από την ουρά προτεραιότητας είναι οι εξής:

  1. priority_queue :: μέγεθος (): Επιστρέφει το μέγεθος της ουράς.
  2. priority_queue :: κενό (): Ελέγχει εάν η ουρά είναι κενή και επιστρέφει την κατάστασή της.
  3. priority_queue :: κορυφή (): Επιστρέφει μια αναφορά στο ανώτατο στοιχείο της ουράς προτεραιότητας.
  4. priority_queue :: push (): Προσθέτει ένα στοιχείο στο τέλος της ουράς προτεραιότητας.
  5. priority_queue :: ποπ (): Καταργεί το πρώτο στοιχείο από την ουρά προτεραιότητας.
  6. priority_queue :: ανταλλαγή (): Χρησιμοποιείται για την ανταλλαγή των περιεχομένων μιας ουράς προτεραιότητας με μια άλλη του ίδιου τύπου και μεγέθους.
  7. τύπος τιμής ουράς προτεραιότητας: Ο τύπος τιμής δίνει τον τύπο του στοιχείου που είναι αποθηκευμένο σε μια ουρά προτεραιότητας. Αυτό λειτουργεί επίσης ως συνώνυμο για την παράμετρο προτύπου.
  8. priority_queue :: emplace (): Χρησιμοποιείται για την εισαγωγή ενός νέου στοιχείου στο κοντέινερ ουράς προτεραιότητας στην κορυφή της ουράς.

Στο επόμενο πρόγραμμα, θα δούμε τη λειτουργικότητα της ουράς προτεραιότητας στο STL στο C ++.

#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << ' '; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << ' Top element of the queue(pq.top()): ' << pq.top(); cout << ' The priority queue pq is : '; displaypq(pq); cout << ' Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; }

Παραγωγή:

πώς να στείλετε μια επίθεση ddos

Μέγεθος της ουράς (σελ. Μέγεθος ()): 5
Κορυφαίο στοιχείο της ουράς (pq.top ()): 9
Η ουρά προτεραιότητας pq είναι: 9 7 5 3 1
Ουρά προτεραιότητας, μετά τη λειτουργία pq.pop (): 7 5 3 1

Εφαρμογή Java για ουρά προτεραιότητας

Η ουρά προτεραιότητας στην java είναι μια ειδική ουρά όπου όλα τα στοιχεία στην ουρά ταξινομούνται σύμφωνα με τη φυσική παραγγελία ή την προσαρμοσμένη παραγγελία χρησιμοποιώντας ένα συγκριτικό που παρέχεται με την ουρά.

Μια ουρά προτεραιότητας στην Java φαίνεται όπως φαίνεται παρακάτω:

Εφαρμογή Java για ουρά προτεραιότητας

Στην ουρά προτεραιότητας Java, τα στοιχεία είναι διατεταγμένα έτσι ώστε το μικρότερο στοιχείο να βρίσκεται στο μπροστινό μέρος της ουράς και το μεγαλύτερο στοιχείο να βρίσκεται στο πίσω μέρος της ουράς. Έτσι, όταν αφαιρούμε το στοιχείο από την ουρά προτεραιότητας, είναι πάντα το μικρότερο στοιχείο που αφαιρείται.

Η κλάση που εφαρμόζει την ουρά προτεραιότητας στην Java είναι 'PriorityQueue' και είναι μέρος του πλαισίου συλλογών της Java. Υλοποιεί τη διεπαφή «Queue» της Java.

Ακολουθεί η ιεραρχία τάξης για την κλάση Java PriorityQueue.

ιεραρχία τάξης για κλάση Java PriorityQueue

Δίνεται παρακάτω ένα παράδειγμα λειτουργικότητας προτεραιότητας ουράς με ακέραιους αριθμούς ως στοιχεία στην Java.

import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println(' After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println(' After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( ' Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i

Παραγωγή:

peek () :: Τιμή κεφαλής: 1
Η ουρά προτεραιότητας:
1 3 5 7
Μετά τη λειτουργία δημοσκόπησης (), ουρά προτεραιότητας:
3 7 5
Μετά τη λειτουργία Κατάργηση (5), ουρά προτεραιότητας:
3 7
Η ουρά προτεραιότητας περιέχει 3 ?: true
Στοιχεία σειράς:
Τιμή: 3
Αξία: 7

Στο παραπάνω πρόγραμμα, χρησιμοποιούμε την κλάση PriorityQueue της Java για να δημιουργήσουμε ένα αντικείμενο του PriorityQueue που περιέχει ένα αντικείμενο Integer. Προσθέτουμε στοιχεία στην ουρά χρησιμοποιώντας τη συνάρτηση 'add'. Στη συνέχεια καλείται η συνάρτηση poll () και διαγράφει το στοιχείο από το μπροστινό μέρος της ουράς που τυχαίνει να είναι το λιγότερο στοιχείο.

Και πάλι καλούμε τη λειτουργία 'remove ()' που αφαιρεί το στοιχείο που καθορίζεται ως παράμετρος από την ουρά. Χρησιμοποιούμε επίσης τη λειτουργία 'Περιέχει ()' για να ελέγξουμε εάν υπάρχει ένα συγκεκριμένο στοιχείο στην ουρά. Τέλος, μετατρέπουμε την ουρά σε ένα αντικείμενο πίνακα χρησιμοποιώντας τη συνάρτηση 'toArray ()'.

Εφαρμογή

  • Χειριστές εξισορρόπησης φορτίου και διακοπής λειτουργικού συστήματος: Λειτουργίες λειτουργικού συστήματος όπως εξισορρόπηση φορτίου και διακοπή του χειρισμού υλοποιείται χρησιμοποιώντας ουρές προτεραιότητας. Η δραστηριότητα εξισορρόπησης φορτίου προγραμματίζει τους πόρους με την υψηλότερη προτεραιότητα προκειμένου να φέρει αποτελεσματικά την εξισορρόπηση φορτίου. Ο χειρισμός διακοπών πραγματοποιείται με την εξυπηρέτηση των διακοπών με την υψηλότερη προτεραιότητα. Αυτή η λειτουργικότητα μπορεί να εφαρμοστεί αποτελεσματικά χρησιμοποιώντας τις ουρές προτεραιότητας.
  • Δρομολόγηση: Η δρομολόγηση είναι μια συνάρτηση που χρησιμοποιείται για τη δρομολόγηση των πόρων του δικτύου, έτσι ώστε να έχουμε μέγιστη απόδοση με ελάχιστο χρόνο ανακύκλωσης. Αυτό μπορεί επίσης να εφαρμοστεί χρησιμοποιώντας την ουρά προτεραιότητας.
  • Έκτακτη ανάγκη νοσοκομείου: Σε μια αίθουσα έκτακτης ανάγκης νοσοκομείου, οι ασθενείς παρακολουθούνται ανάλογα με το πόσο σοβαρή είναι η κατάσταση του ασθενούς. Αυτό μπορεί να προσομοιωθεί χρησιμοποιώντας ουρές προτεραιότητας.
  • Ο πιο σύντομος αλγόριθμος διαδρομής της Dijkstra: Εδώ το γράφημα αποθηκεύεται ως λίστα γειτνίασης και μπορούμε να χρησιμοποιήσουμε μια ουρά προτεραιότητας για να εξαγάγουμε αποτελεσματικά το ελάχιστο σταθμισμένο άκρο από τη λίστα γειτνίασης για να εφαρμόσουμε τον αλγόριθμο βραχύτερης διαδρομής της Dijkstra.
  • Η ουρά προτεραιότητας μπορεί επίσης να χρησιμοποιηθεί για την αποθήκευση κλειδιών κόμβων και την εξαγωγή του ελάχιστου κόμβου κλειδιού κατά την εφαρμογή του δέντρου έκτασης.

συμπέρασμα

Οι ουρές προτεραιότητας δεν είναι παρά η επέκταση της ουράς. Αλλά σε αντίθεση με τις ουρές που προσθέτουν / αφαιρούν στοιχεία χρησιμοποιώντας την προσέγγιση FIFO, στην ουρά προτεραιότητας τα στοιχεία αφαιρούνται από την ουρά σύμφωνα με την προτεραιότητα. Έτσι, κάθε στοιχείο στην ουρά συσχετίζεται με προτεραιότητα και το στοιχείο με την υψηλότερη προτεραιότητα είναι το πρώτο που αφαιρείται από την ουρά.

Η ουρά προτεραιότητας έχει τρεις κύριες λειτουργίες, δηλαδή εισάγετε (), getHighestPriority () και deleteHighestPriority (). Η ουρά προτεραιότητας μπορεί να εφαρμοστεί χρησιμοποιώντας πίνακες ή συνδεδεμένη λίστα, αλλά η λειτουργία δεν είναι πολύ αποτελεσματική. Η ουρά προτεραιότητας μπορεί επίσης να εφαρμοστεί χρησιμοποιώντας σωρούς και η απόδοση είναι πολύ πιο γρήγορη.

Στο C ++, έχουμε επίσης μια κλάση κοντέινερ που εφαρμόζει τη λειτουργικότητα μιας ουράς προτεραιότητας. Στην Java, υπάρχει μια ενσωματωμένη κατηγορία priority_queue που παρέχει τη λειτουργικότητα μιας ουράς προτεραιότητας.

Η ουρά προτεραιότητας χρησιμοποιείται κυρίως σε εφαρμογές που απαιτούν επεξεργασία αντικειμένων σύμφωνα με την προτεραιότητα. Για παράδειγμα, χρησιμοποιείται στον χειρισμό διακοπής.

Το επερχόμενο σεμινάριό μας θα διερευνήσει τα πάντα σχετικά με την κυκλική ουρά που είναι μια ακόμη επέκταση της ουράς.

=> Επισκεφθείτε εδώ για το πλήρες μάθημα C ++ από ειδικούς.

Συνιστώμενη ανάγνωση

^