• Ανακοινώθηκε: 5/5/2025
• Προθεσμία παράδοσης: 26/5/2025 23:59
• 16% του συνολικού βαθμού στο μάθημα
• Link εγγραφής: https://classroom.github.com/a/uY-XBRfM
• Repository: https://github.com/chatziko-k08/2025-project-2-<github-username>

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

Στην εργασία αυτή καλείστε να δημιουργήσετε σταδιακά διάφορες βελτιώσεις και παραλλαγές του ADTPriorityQueue.

Σημειώσεις:

• όλες οι συναρτήσεις προς υλοποίηση σε όλες τις ασκήσεις είναι εξαιρετικά απλές, καμία δεν απαιτεί παραπάνω από 10-20 γραμμές κώδικα (συχνά και πολύ λιγότερο). Ο σκοπός της εργασίας είναι η κατανόηση των δομών, όχι η παραγωγή τεράστιου όγκου κώδικα.

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

• Για όλες τις ασκήσεις, αναφέρετε στο README.md την πολυπλοκότητα κάθε λειτουργίας που υλοποιήσατε (η οποία πιθναόν να εξαρτάται από την υλοποίηση των ADTs που χρησιμοποιεί η συγκεκριμένη λειτουργία).

Άσκηση 1 (20%)

Ένας σημαντικός περιορισμός της κλασικής ουράς προτεραιότητας είναι ότι επιτρέπει τη διαγραφή μόνο του μεγαλύτερου στοιχείου. Η πρώτη βελτίωση που θα κάνουμε προσθέτει τη δυνατότητα διαγραφής οποιουδήποτε στοιχείου μέσω της λογικής των “κόμβων”:

• Η pqueue_insert επιστρέφει τον “κόμβο” (τύπος PriorityQueueNode) που περιέχει το νέο στοιχείο.
• Η pqueue_remove_max αντικαθίσταται από την pqueue_remove που παίρνει όρισμα τον κόμβο προς διαγραφή.
• Η pqueue_max_node επιστρέφει τον κόμβο που περιέχει τη μέγιστη τιμή.
• Η pqueue_node_value επιστρέφει την τιμή ενός κόμβου.

Το interface του module (include/ADTPriorityQueue.h) στο repository της εργασίας έχει τροποποιηθεί με βάση τις παραπάνω προσθήκες. Επίσης το test του module (tests/ADTPriorityQueue_test.c) έχει επίσης τροποποιηθεί και ελέγχει τις παραπάνω λειτουργίες (δεν χρειάζεται να αλλάξετε το test, εκτός αν το επιθυμείτε).

Η απλούστερος τρόπος να υλοποιήσουμε μια τέτοια ουρά προτεραιότητας είναι μέσω του ADT Set που παρέχει έτοιμες όλες τις λειτουργίες που θέλουμε (καθώς και την λογική των κόμβων). Στο αρχείο modules/UsingADTSet/ADTPriorityQueue.c υπάρχει η δομή μιας τέτοιας υλοποίησης την οποία καλείστε να επεκτείνετε.

Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks. Το tests/Makefile έχει ήδη ρυθμιστεί ώστε να παράγει το εκτελέσιμο του test.

Σημείωση: η λογική των κόμβων χρησιμοποιείται μόνο στη διαγραφή, ο ADT δεν επιτρέπει τη διάσχιση των στοιχείων (δεν υπάρχουν δηλαδή συναρτήσεις next,prev, κλπ).

Άσκηση 2 (20%)

Η δεύτερη επέκταση της κλασικής ουράς προτεραιότητας που θα εξετάσουμε είναι η ουρά προτεραιότητας δύο άκρων (Double-Ended Priority Queue ή DEPQ). Μία DEPQ παρέχει πρόσβαση ταυτόχρονα στο μεγαλύτερο και στο μικρότερο στοιχείο, και επιτρέπει την αφαίρεση και από τα δύο “άκρα”.

Στο αρχείο include/ADTDEPQ.h υπάρχει το interface αυτού του ADT, το οποίο περιέχει τις κλασικές συναρτήσεις της ουράς προτεραιότητας, με την προσθήκη των:

• depq_min: επιστρέφει το μικρότερο στοιχείο.
• depq_remove_min: αφαιρεί το μικρότερο στοιχείο.

Η απλούστερη υλοποίηση του ADT DEPQ είναι επίσης μέσω του ADT Set, όπως στην προηγούμενη άσκηση (χρειάζονται πραγματικά ελάχιστες αλλαγές σε σχέση με την Άσκηση 1). Προσθέστε ένα αρχείο modules/UsingADTSet/ADTDEPQ.c με την υλοποίηση αυτή. Προσθέστε επίσης tests στο tests/ADTDEPQ_test.c τα οποία η υλοποίησή σας θα πρέπει να περνάει χωρίς leaks.

Άσκηση 3 (20%)

Η τρίτη επέκταση της κλασικής ουράς προτεραιότητας που θα εξετάσουμε είναι η $k$-Priority Queue (KPQ) η οποία παρέχει πρόσβαση τόσο στο μέγιστο όσο και στο $k$-οστό σε διάταξη στοιχείο (για ένα σταθερό $k$ που δίνεται κατά τη δημιουργία της ουράς). Το interface του ADT αυτού δίνεται στο include/ADTKPQ.h.

Μπορούμε φυσικά να υλοποιήσουμε ένα KPQ μέσω του ADT Set, όπως κάναμε προηγουμένως, αλλά θα επιλέξουμε μια πιο ευέλικτη υλοποίηση: μέσω του ADT DEPQ (Άσκηση 2). Πιο συγκεκριμένα:

• Διατηρούμε μία DEPQ μεγέθους το πολύ $k$ με τα $k$ μεγαλύτερα στοιχεία.
• Kαι μια κλασική Priority Queue με τα υπόλοιπα.
• Εισαγωγή: προσθέτουμε το στοιχείο στο DEPQ. Αν το DEPQ ξεπεράσει τα $k$ στοιχεία, αφαιρούμε το μικρότερο και το προσθέτουμε στο PQ.
• Διαγραφή: αφαιρούμε το μεγαλύτερο στοιχείο του DEPQ. Αν το PQ δεν είναι κενό αφαιρούμε το μεγαλύτερο στοιχείο και το προσθέτουμε στο DEPQ.

Προσθέστε ένα αρχείο modules/UsingADTDEPQ/ADTKPQ.c με την υλοποίηση αυτή. Προσθέστε επίσης tests στο tests/ADTKPQ_test.c τα οποία η υλοποίησή σας θα πρέπει να περνάει χωρίς leaks.

Bonus 1 (5%): προσθέστε και μια υλοποίηση μέσω ADT Set, φροντίζοντας ώστε οι kpq_max και kpq_k_th να είναι $Ο(1)$.

Άσκηση 4 (20%)

Μέχρι στιγμής όλες μας οι υλοποιήσεις βασίζονται (άμεσα ή έμμεσα) στο ADT Set. Το πρόβλημα με την προσέγγιση αυτή είναι ότι χρησιμοποιούμε έναν σχετικά σύνθετο τύπο (Set) για να υλοποιήσουμε έναν απλούστερο (Priority Queue). Αυτό στην πράξη είναι μη βέλτιστο τόσο σε χρόνο όσο και σε μνήμη. Στη συνέχεια θα δούμε ότι μπορούμε αρκετά εύκολα να υλοποιήσουμε τους παραπάνω ADTs με απλούς σωρούς, χωρίς την επιπλέον πολυπλοκότητα του Set.

Ξεκινάμε με τη διαγραφή οποιουδήποτε στοιχείου μέσω της λογικής των “κόμβων”. Θέλουμε να τροποποιήσουμε την κλασική υλοποίηση μέσω σωρού (modules/UsingHeap/ADTPriorityQueue.c) προσθέτωντας τους κόμβους και τις συναρτήσεις της Άσκησης 1.

Μια απλή ιδέα είναι ένας κόμβος (PriorityQueueNode) να είναι απλά ένας int pointer που περιέχει τη θέση του αντίστοιχου στοιχείου στο vector values. Αν δηλαδή η pqueue_insert προσθέσει το στοιχείο στη θέση i του vector, τότε θα πρέπει να επιστρέψει έναν int* με την τιμή i. Έτσι όταν περάσουμε τον κόμβο στην pqueue_remove, η συνάρτηση θα καταλάβει ποιο στοιχείο θέλουμε να αφαιρέσουμε.

Το βασικό πρόβλημα, βέβαια, είναι ότι τα στοιχεία στο σωρό μετακινούνται, οπότε το στοιχείο που προστέθηκε στη θέση i δε θα παραμείνει για πάντα εκεί. Αν μετακινηθεί στη θέση j τότε πρέπει να φροντίσουμε να ενημερώσουμε το node που επιστρέψαμε στο χρήση, αλλιώς το remove θα αφαιρέσει λάθος στοχείο! Για να γίνει αυτό:

• Αποθηκεύουμε όλα τα nodes (int*) σε ένα vector nodes, έτσι ώστε το nodes[i] να αντιστοιχεί στο values[i] (δηλαδή να περιέχει τη θέση i).
• και φροντίζουμε η node_swap (που καλείται από τις bubble_up, bubble_down) να ενημερώνει κατάλληλα τα nodes. Οταν κάνουμε swap τα i και j, το swap πρέπει να γίνει και στα δύο vectors, και επιπλέον οι τιμές των nodes που κάναμε swap πρέπει επίσης να ενημερωθούν.

Το ίδιο το remove από την άλλη δεν αλλάζει, απλά ανταλλάσουμε το στοιχείο που αφαιρείται με το τελευταίο και κάνουμε bubble down (απλά δε θα γίνει στη ρίζα, αλλά στη θέση του στοιχείου που αφαιρείται).

Επεκτείνετε την υλοποίηση του modules/UsingHeap/ADTPriorityQueue.c με βάση τις παραπάνω οδηγίες. Γενικά χρειάζονται ελάχιστες αλλαγές (30-40 γραμμές κώδικα για όλες τις λειτουργίες μαζί), το βασικό είναι να καταλάβουμε τη λογική και ποια σημεία πρέπει να αλλάξουμε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχουν test (modules/UsingADTSet/ADTPriorityQueue.c) χωρίς leaks.

Άσκηση 5 (20%)

Τέλος, μπορούμε να υλοποιήσουμε ένα DEPQ (Άσκηση 2) μέσω σωρού, αποφεύγοντας τη χρήση του ADT Set. Μάλιστα, μια “καθαρή” λύση είναι να μην χρησιμοποιήσουμε καν το σωρό κατευθείαν, αλλά το ADT Priority Queue (με τις επεκτάσεις που προσθέσαμε).

Η λογική είναι απλή:

• Θα διατηρούμε δύο ουρές, μία για το μέγιστο και ένα μία το ελάχιστο (με αντίθετη διάταξη).
• Η εύρεση του μέγιστου/ελάχιστου γίνεται εύκολα από την αντίστοιχη ουρά.
• Η προσθήκη θα γίνεται και στις δύο ουρές.
• Η remove_max (και συμμετρικά ή remove_min) θα αφαιρεί το στοιχείο αρχικά από την ουρά του μέγιστου.
• Αλλά μετά θα πρέπει προφανώς το στοιχείο να αφαιρεθεί και από τη δεύτερη ουρά.

Το τελευταίο task (διαγραφή από τη δεύτερη ουρά) είναι και το πιο δύσκολο, και απαιτεί τη χρήση των κόμβων και της pqueue_remove που επιτρέπει την αφαίρεση οποιουδήποτε στοιχείου.

Προσοχή:

• Στις δύο ουρές δεν βάζουμε απλά τα στοιχεία, αλλά ένα struct με όλες τις πληροφορίες που θα χρειαστούμε στην υλοποίηση (πχ τα PriorityQueueNodes που επιστρέφουν οι δύο pqueue_insert.
• Επίσης θα πρέπει να φτιάξετε συναρτήσεις compare που να συγκρίνουν τα structs αυτά.
• Και να βρείτε τρόπο στη δεύτερη ουρά να κάνετε τη σύγκριση αντεστραμμένη!

Προσθέστε την υλοποίηση αυτή στο αρχείο modules/UsingADTPriorityQueue/ADTDEPQ.c. Η υλοποίηση θα πρέπει να περνάει (χωρίς τροποποίηση):

• Το tests/ADTDEPQ_test.c που φτιάξατε στην Άσκηση 2.
• Το tests/ADTΚPQ_test.c της Άσκησης 3, όπου το KPQ υλοποιείται μέσω DEPQ.

Στα παραπάνω tests ο ADT Priority Queue θα πρέπει να είναι αυτός της Άσκησης 4 μέσω Heap. Πχ για τα KPQ tests η αλυσίδα των dependencies είναι:

   tests/ADTΚPQ_test.c
=> modules/UsingADTDEPQ/ADTKPQ.c
=> modules/UsingADTPriorityQueue/ADTDEPQ.c
=> modules/UsingHeap/ADTPriorityQueue.c

Bonus 2 (10%):

Προσθέστε μια υλοποίηση του DEPQ μέσω min-max heap, που μας επιτρέπει να έχουμε μία ενιαία δομή, χωρίς dependencies και χωρίς την ανάγκη για δύο ουρές (και διπλή μνήμη).