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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

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

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

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

Υλοποίηση[Επεξεργασία | επεξεργασία κώδικα]

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