Τι είναι η δομή δεδομένων priority_queue;

priority_queue — ένας προσαρμογέας δοχείου από τη βιβλιοθήκη C++ που παρέχει λειτουργικότητα ουράς με προτεραιότητα. Τα στοιχεία εξάγονται με βάση τη προτεραιότητά τους (κατά προεπιλογή, το μεγαλύτερο στοιχείο έχει την υψηλότερη προτεραιότητα). Στην ουσία, είναι ένα περίβλημα πάνω σε ένα άλλο δοχείο (κατά προεπιλογή std::vector), που χρησιμοποιεί αλγορίθμους σωρού (std::make_heap, std::push_heap, std::pop_heap) για να διατηρεί τη δομή σωρού μέσα στο βασικό δοχείο.

Βασικά χαρακτηριστικά:

• Προτεραιότητα: Τα στοιχεία εξάγονται σύμφωνα με την προτεραιότητά τους. Κατά προεπιλογή, χρησιμοποιείται το std::less για τον ορισμό της προτεραιότητας, που σημαίνει ότι το μεγαλύτερο στοιχείο θεωρείται ότι έχει την υψηλότερη προτεραιότητα (μέγιστο σωρό). Μπορεί να αλλάξει η σειρά, παρέχοντας έναν διαφορετικό συγκριτή, π.χ. std::greater για ελάχιστο σωρό.
• Προσαρμογέας: Το priority_queue δεν είναι αυτόνομο δοχείο, αλλά προσαρμόζει ένα άλλο βασικό δοχείο (συνήθως std::vector, αλλά μπορεί να είναι και άλλο, π.χ. std::deque), παρέχοντας διεπαφή ουράς με προτεραιότητα.
• Σωρός: Υλοποιείται εσωτερικά με χρήση σωρού, που εξασφαλίζει λογαριθμική πολυπλοκότητα για τις λειτουργίες εισαγωγής και εξαγωγής.
• Μη ταξινομημένη πρόσβαση: Δεν παρέχει τυχαία πρόσβαση στα στοιχεία. Διαθέσιμες είναι μόνο οι λειτουργίες εισαγωγής (push), εξαγωγής του στοιχείου με την υψηλότερη προτεραιότητα (pop) και προβολής του στοιχείου με την υψηλότερη προτεραιότητα (top).

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

Λειτουργία	Περιγραφή	Πολυπλοκότητα (μέση/χειρότερη περίπτωση)
push	Εισάγει ένα στοιχείο με καθορισμένη προτεραιότητα.	O(log N)
pop	Αφαιρεί το στοιχείο με την υψηλότερη προτεραιότητα.	O(log N)
top	Επιστρέφει σταθερή αναφορά στο στοιχείο με την υψηλότερη προτεραιότητα.	O(1)
empty	Ελέγχει αν η ουρά είναι κενή.	O(1)
size	Λαμβάνει τον αριθμό των στοιχείων στην ουρά.	O(1)

Παράδειγμα χρήσης:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // για std::greater

int main() {
    // Μέγιστος σωρός (κατά προεπιλογή)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Στοιχεία μέγιστου σωρού (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Ελάχιστος σωρός (χρησιμοποιώντας std::greater<int>)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

    std::cout << "Στοιχεία ελάχιστου σωρού (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Χρησιμοποιείται σε αλγόριθμους όπου απαιτείται συνεχής εξαγωγή του στοιχείου με την υψηλότερη (ή χαμηλότερη) προτεραιότητα, π.χ. ο αλγόριθμος Dijkstra, ο αλγόριθμος Prim ή σε προσομοιώσεις γεγονότων.