Ουρές Προτεραιότητας(Priority Queues).

Η ουρά προτεραιότητας είναι μια δομή που περιέχει στοιχεία τα οποία έχουν μια επιπρόσθετη πληροφορία την  προτεραιότητα.
Στην ουρά προτεραιότητας υπάρχουν τρεις βασικές πράξεις η εισαγωγή στοιχείου(insert) η εύρεση του στοιχείου με τη μεγαλύτερη προτεραιότητα(findMax)και η απομάκρυνση στοιχείου με τη μεγαλύτερη προτεραιότητα(deleteMax).

Εικόνα 1: Βασικό μοντέλο μιας ουράς προτεραιότητας

Η εισαγωγή στοιχείου κάνει το αυτονόητο εισάγει δηλαδή το νέο στοιχείο στη δομή. Το πώς θα τοποθετηθεί το στοιχείο μπορεί να εξαρτάται και από την προτεραιότητά του.
Η απομάκρυνση στοιχείου όμως απομακρύνει πάντα από τη δομή το στοιχείο με τη μεγαλύτερη προτεραιότητα. Γίνεται επομένως κατανοητό πως η δομή πρέπει να περιέχει τέτοιους μηχανισμούς ώστε να μπορεί να βρίσκει το στοιχείο με τη μεγαλύτερη προτεραιότητα όσο γίνεται πιο γρήγορα.
Η ουρά προτεραιότητας που μελετάμε σε αυτήν την ενότητα χρησιμοποιεί τη δομή σωρού (Heap ) ως δομή αποθήκευσης των στοιχείων της. Το πλεονέκτημα αυτής της δομής είναι ότι  το μεγαλύτερο στοιχείο βρίσκεται πάντα στη ρίζα. Έτσι η απομάκρυνσή του γίνεται σε Ο(1) βήματα. Βέβαια μετά την απομάκρυνση του στοιχείου με τη μεγαλύτερη προτεραιότητα πρέπει να γίνουν κάποιες διορθωτικές ρυθμίσεις.
Τελικά με χρήση σωρού τόσο η εισαγωγή όσο και η απομάκρυνση κοστίζουν Ο(logN) όπου Ν το πλήθος των στοιχείων του σωρού. Πιο απλά οι δύο αλγόριθμοι στη χειρότερη περίπτωση θα κάνουν (2*ύψος δέντρου Σωρού) συγκρίσεις.
Για περισσότερες λεπτομέρειες για το τι είναι σωρός δείτε τις βασικές λειτουργίες σωρού.