Ουρά προτεραιότητας (δομή δεδομένων)

Στην πληροφορική, μια ουρά προτεραιότητας είναι ένας αφηρημένος τύπος δεδομένων που μοιάζει με την απλή ουρά ή την στοίβα, αλλά διαφέρει στο ότι η προτεραιότητα κάθε στοιχείου δεν εξαρτάται από την σειρά εισαγωγής του στην ουρά, αλλά από μια τιμή που καλείται κλειδί του στοιχείου. Το κλειδί των στοιχείων πρέπει να είναι ένας συγκρίσιμος τύπος δεδομένων, δηλαδή δύο οποιαδήποτε στοιχεία αυτού του τύπου δεδομένων πρέπει να μπορούν να συγκρίνονται. Για παράδειγμα, ο boolean τύπος δεδομένων δεν είναι συγκρίσιμος (γιατί δεν υπάρχει διάταξη μεταξύ των τιμών αληθείας), αλλά ο ακέραιος τύπος δεδομένων είναι.

Όπως και στην απλή ουρά και στη στοίβα, η ουρά προτεραιότητας παρέχει τις εξής πράξεις:

• insert(element, key), για την εισαγωγή ενός στοιχείου με ένα κλειδί και
• extract_highest_priorty(), για την επιστροφή και διαγραφή του πρώτου σε προτεραιότητα στοιχείου. Είναι σημαντικό να αναφερθεί ότι η ουρά προτεραιότητας δεν παρέχει πρόσβαση σε όλα τα στοιχεία της, παρά μόνο σε αυτό με την μεγαλύτερη προτεραιότητα.

Μια ουρά προτεραιότητας μπορεί να είναι ουρά προτεραιότητας ελαχίστου ή ουρά προτεραιότητας μεγίστου ή και τα δύο. Στην πρώτη περίπτωση, το στοιχείο με την μεγαλύτερη προτεραιότητα είναι αυτό που έχει το μικρότερο κλειδί, ενώ στη δεύτερη περίπτωση είναι αυτό που έχει το μεγαλύτερο κλειδί. Και οι δύο παραλλαγές είναι ισοδύναμες, με την έννοια ότι έχουν την ίδια ακριβώς δομή και η διαφορά τους έγκειται μόνο στην προτεραιότητα ελαχίστου και μεγίστου. Μια ουρά προτεραιότητας ελαχίστου και μεγίστου είναι μια βελτιωμένη παραλλαγή μιας ουράς προτεραιότητας, η οποία υποστηρίζει μία ακόμη πράξη, την extract_lowest_priorty(), για την εξαγωγή του στοιχείου με την μικρότερη προτεραιότητα. Οι παραλλαγές της ουράς προτεραιότητας ποικίλουν και η κάθε μία μπορεί να υποστηρίζει επιπλέον πράξεις από τις δύο βασικές.

Υλοποίηση

Η ουρά προτεραιότητας μπορεί να υλοποιηθεί με χρήση διάφορων δομών δεδομένων. Μια πολύ απλή μορφή υλοποίησης είναι με την χρήση ενός μη ταξινομημένου πίνακα όπου η προσθήκη ενός νέου στοιχείου γίνεται γρήγορα O(1) και η αφαίρεση στοιχείου με μέγιστη προτεραιότητα γίνεται με προσπέλαση στα μη ταξινομημένα στοιχεία του πίνακα O(n). Η συνηθέστερη υλοποίηση γίνεται με την δενδρική δομή του σωρού, με τον οποίο οι διαδικασίες insert(element, key) και extract_highest_priorty() γίνονται σε χρόνο Ο(logn) και η διαδικασία της κατασκευής μιας ουράς προτεραιότητας με n στοιχεία μπορεί να πάρει γραμμικό χρόνο (Ο(n)). Στην περίπτωση υλοποίησης της ουράς προτεραιότητας με πίνακα (ή και με συνδεδεμένη λίστα) όπου κάθε στοιχείο την ώρα που εισάγεται μπαίνει στην κατάλληλη θέση ώστε ο πίνακας/λίστα να είναι ταξινομημένος/η έχουμε εισαγωγή σε χρόνο O(N) και απομάκρυνση στοιχείου με μεγαλύτερη προτεραιότητα σε χρόνο O(1).

C++

Στην γλώσσα C++ η ουρά προτεραιότητας είναι υλοποιημένη στην Πρότυπη βιβλιοθήκη C++ στην δομή priority_queue<..>, θεωρείται δομή περιέχοντα (Αγγλικά: container). Παίρνει τρεις παραμέτρους, το αντικείμενο του περιέχοντα (στο παρακάτω παράδειγμα είναι ο int / ακέραιος), η περιέχοντα δομή όπου θα αποθηκευτούν τα στοιχεία (εδώ βάλαμε τον περιέχοντα vector<..>) και ένα αντικείμενο σύγκρισης (στο παρακάτω παράδειγμα ορίσαμε το struct compare, αλλιώς το προκαθορισμένο είναι το less<T>).

#include <iostream>
#include <queue>
 
using namespace std;
 
struct compare {
   bool operator()(const int& l, const int& r) {
      return l > r;
  }
};
 
int main() {
   priority_queue<int,vector<int>, compare > pq;
 
   pq.push(3);
   pq.push(5);
   pq.push(1);
   pq.push(8);
   while (!pq.empty()) {

      // εμφανίζει: 1 3 5 8
      cout << pq.top() << endl;    // επιστρέφει το στοιχείο με τη μέγιστη προτεραιότητα
                                   // όπως έχει οριστεί με βάση την δομή σύγκρισης compare struct
      pq.pop();                    // αφαιρεί το στοιχείο με τη μέγιστη προταιρεότητα
   }
 
   return 0;
}