Υλοποίηση της ουράς προτεραιότητας με Heap(σωρός).

Η υλοποίηση της ουράς προτεραιότητας που θα μελετήσουμε σε αυτή την ενότητα  γίνεται με τη βοήθεια του δυαδικού σωρού(binary heap). Η υλοποίηση αυτή είναι η πιο συνηθισμένη και προσφέρει καλούς χρόνους εισαγωγής και απομάκρυνσης στοιχείου. Ο σωρός σαν δομή χαρακτηρίζεται από δύο ιδιότητες την ιδιότητα δομής σωρού και την ιδιότητα  σωρού.

Η ιδιότητα δομής  και η ιδιότητα σωρού.

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

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

Η εισαγωγή και η απομάκρυνση στοιχείων στην ουρά προτεραιότητας  συνεπάγεται πλέον σε αυτήν την υλοποίηση   εισαγωγή και απομάκρυνση στοιχείο στο σωρό. Εδώ λοιπόν μελετάμε αυτές τις δύο βασικές λειτουργίες του σωρού.
Παρόλο που ο σωρός στην αρχή είναι άδειος δεσμεύουμε προκαταβολικά MaxN θέσεις μνήμης. Οι θέσεις των στοιχείων του σωρού προσπελάσονται μέσω του πίνακα array. Η ρίζα του σωρού βρίσκεται στη θέση array[1] ενώ το αριστερό και δεξιό παιδί ενός στοιχείου στη θέση i βρίσκονται στις θέσεις 2i και 2i+1 αντίστοιχα. Η μεταβλητή currentSize μας πληροφορεί για το τρέχον πλήθος των στοιχείων του σωρού. Αν ο σωρός περιέχει MaxN στοιχεία δηλαδή currentSize=MaxN τότε λέμε ότι ο σωρός είναι γεμάτος και δε μπορούμε να εισάγουμε νέα στοιχεία. Αντίστοιχα αν ο σωρός είναι άδειος δε μπορούμε να εξάγουμε στοιχεία από αυτόν.

Εισαγωγή στοιχείου (insert).

Όταν εισάγουμε ένα καινούργιο στοιχείο στο σωρό αυτό τοποθετείται στην επόμενη διαθέσιμη θέση στο τελευταίο επίπεδο. Αν η τιμή του σωρού δεν παραβιάζει την ιδιότητα του σωρού (δηλαδή η τιμή του είναι μικρότερη η ίση από αυτή του γονέα του) τότε το στοιχείο μένει στη θέση του. Σε διαφορετική περίπτωση παιδί και γονέας ανταλλάσσουν θέσεις. Αυτή η διαδικασία συνεχίζεται μέχρι το καινούργιο στοιχείο να βρει μια θέση τέτοια ώστε να ικανοποιείται η ιδιότητα του σωρού. Έτσι κάθε στοιχείο που εισάγεται στο σωρό θα πρέπει να διασχίσει ένα μονοπάτι από το φύλλο στο οποίο βρισκόταν αρχικά μέχρι κάποιον κατάλληλο εσωτερικό κόμβο. Στη χειρότερη περίπτωση το μονοπάτι θα είναι ως τη ρίζα του δέντρου.
Ο χρόνος εισαγωγής ενός στοιχείου στο δέντρο είναι O(logN) όπου N το πλήθος των στοιχείων του σωρού. Στη χειρότερη περίπτωση θα χρειαστούν τόσα βήματα όσο και το ύψος του δέντρου.

Ψευδοκώδικας για την εισαγωγή νέου στοιχείου στο σωρό.(Insert(x))

Εύρεση του μεγαλύτερου στοιχείου(findMax).

Το μεγαλύτερο στοιχείο της δομής λόγω της ιδιότητας του σωρού βρίσκεται στη ρίζα. Έτσι το στοιχείο αυτό βρίσκεται άμεσα αφού είναι το πρώτο στοιχείο του πίνακα array.
maxItem=array[1]

Απομάκρυνση μεγαλύτερου στοιχείου(deleteMax).

Η εύρεση του μεγαλύτερου στοιχείου λόγω της ιδιότητας του σωρού είναι εύκολη. Το δύσκολο τμήμα της διαδικασίας είναι η απομάκρυνση του. Το μεγαλύτερο στοιχείο βρίσκεται πάντα στη ρίζα αλλά όταν το απομακρύνουμε δημιουργείται ένα κενό. Το κενό πρέπει να καλυφτεί με τέτοιο τρόπο ώστε ο σωρός να τηρεί την ιδιότητα του σωρού. 
Μετά την απομάκρυνση του μεγαλύτερου στοιχείου τοποθετείται στη ρίζα το τελευταίο στοιχείο του σωρού (αυτό δηλαδή με δείκτη currentSize) και το τρέχον μέγεθος μειώνεται κατά ένα. Αν το στοιχείο που περιέχει τώρα η ρίζα είναι μεγαλύτερο ή ίσο με τα παιδιά του μένει ως έχει. Σε διαφορετική περίπτωση το μεγαλύτερο παιδί παίρνει τη θέση του γονέα και αυτό συνεχίζεται μέχρι το στοιχείο που ήταν στη ρίζα να βρεθεί σε μία θέση στο σωρό που οι τιμές των παιδιών του να μην είναι μεγαλύτερες από τη δικιά του.
Και σε αυτήν τη περίπτωση ο χρόνος διαγραφής είναι O(logN) όπου N το πλήθος των στοιχείων του σωρού.

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