Εργασία 2

Last updated on May 29, 2026

Σημαντικό: διαβάστε τις οδηγίες (κοινές για όλες τις εργασίες). Μην ξεχάσετε να συμπληρώσετε το αρχείο AUTHORS. Αν δεν το συμπληρώσετε, ή αν η εργασία σας δεν κάνει compile στοv αυτόματο έλεγχο που γίνεται σε κάθε push, θα πάρετε email λάθους και θα εμφανιστεί ένα ❌ στο GitHub. Μπορείτε να δείτε ακριβώς τι λάθος συνέβη στην καρτέλα “Actions” στο GitHub.

Γενικά

Στην εργασία αυτή καλείστε να δημιουργήσετε διαφορετικές υλοποιήσεις του ADT Mergeable Priority Queue (MPQ). Ο αφηρημένος αυτός τύπος δεδομένων παρέχει όλες τις λειτουργίες της κλασικής ουράς προτεραιότητας, και επιπλέον επιτρέπει τη συγχώνευση δύο ουρών:

// Συγχωνεύει την ουρά mpq2 στην ουρά mpq. Μετά την κλήση η mpq περιέχει το
// σύνολο των στοιχείων των δύο ουρών, ενώ η mpq2 έχει καταστραφεί (η χρήση της
// μετά το merge είναι μη ορισμένη). Η συγχώνευση απαιτεί η διάταξη και η
// συνάρτηση destroy των δύο ουρών να είναι η ίδια (διαφορετικά η συμπεριφορά
// είναι μη ορισμένη).

void mpq_merge(MPQ mpq, MPQ mpq2);

Σημειώσεις:

  • Η Εργασία 2 είναι αρκετά απλούστερη από την Εργασία 1. Ειδικά οι Ασκήσεις 1-4 χρειάζονται ελάχιστο κώδικα (η μόνη λίγο πιο απαιτητική είναι η Άσκηση 5).

  • Κάθε άσκηση μπορεί να υλοποιηθεί ανεξάρτητα, δεν χρειάζεται να γίνουν με τη σειρά.

  • Το test tests/ADTMPQ.c δίνεται έτοιμο και καλύπτει όλες τις λειτουργίες του ADT MPQ. Δεν χρειάζεται να αλλάξετε το test (εκτός αν το επιθυμείτε). Επίσης το tests/Makefile έχει ήδη ρυθμιστεί ώστε να παράγει εκτελέσιμα του test για όλες τις υλοποιήσεις.

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

Άσκηση 1 - Υλοποίηση μέσω ADT PriorityQueue (20%)

Δημιουργήστε μια πολύ απλή υλοποίηση του ADT MPQ, αποθηκεύοντας τα δεδομένα σε ένα κλασσικό ADT PriorityQueue (το οποίο το παίρνετε έτοιμο). Για κάθε λειτουργία του MPQ απλά καλείτε την αντίστοιχη λειτουργία του PriorityQueue.

Η νέα λειτουργία mpq_merge υλοποιείται με απλούστατο (αν και αργό) τρόπο: αφαιρείτε διαδοχικά τα στοιχεία από το mpq2 και τα προσθέτετε στο mpq. Προσέξτε μόνο να μην κληθεί η destroy function στα στοιχεία αυτά (αφού δεν αφαιρούνται, απλά συγχωνεύονται).

Στο αρχείο modules/UsingADTPriorityQueue/ADTMPQ.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Άσκηση 2 - Υλοποίηση μέσω Unsorted Linked List (20%)

Η δεύτερη υλοποίηση που καλείστε να φτιάξετε χρησιμοποιεί μια συνδεδεμένη λίστα χωρίς ταξινόμηση, διατηρώντας επίσης έναν pointer στο μέγιστο στοιχείο της λίστας. Η εισαγωγή είναι γρήγορη, εισάγοντας το στοιχείο και ενημερώνοντας τον pointer. Η διαγραφή, από την άλλη, είναι αναγκαστικά αργή.

Η νέα λειτουργία mpq_merge υλοποιείται πολύ εύκολα συγχωνεύοντας τις δύο λίστες, το οποίο θα πρέπει να κάνετε σε $O(1)$. Χρησιμοποιήστε τη δική σας υλοποίηση λίστας, καθώς ο ADT List δεν έχει λειτουργία συγχώνευσης (μπορείτε βέβαια, αν θέλετε, να πάρετε κώδικα από την υλοποίηση του ADT List στο lecture-code).

Στο αρχείο modules/UsingLinkedList/ADTMPQ.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Άσκηση 3 - Υλοποίηση μέσω Heap (20%)

Η τρίτη υλοποίηση που καλείστε να φτιάξετε χρησιμοποιεί έναν σωρό, όπως κάναμε και με το κλασικό Priority Queue. Όλες οι βασικές λειτουργίες είναι ολόιδιες, μπορείτε να πάρετε copy-paste τον κώδικα από το modules/UsingHeap/ADTPriorityQueue.c.

Η νέα λειτουργία mpq_merge υλοποιείται πιο γρήγορα από την απλή διαδοχική εισαγωγή (της Άσκησης 1) ως εξής: προσθέτουμε όλα τα στοιχεία από το mpq2->values στο mpq->values και τρέχουμε τον αλγόριθμο heapify που είδαμε στις διαλέξεις και στο Εργαστήριο 4.

Στο αρχείο modules/UsingHeap/ADTMPQ.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Άσκηση 4 - Δημιουργία MPQ από αρχικά δεδομένα (20%)

Θα παρατηρήσατε ίσως ότι η mpq_create, σε αντίθεση με την pqueue_create, δεν επιτρέπει τη δημιουργία μιας ουράς με αρχικά δεδομένα. Ο λόγος είναι ότι η λειτουργία αυτή είναι “πλεονάζουσα”, δεν έχουμε ανάγκη να μας την παρέχει το module, μπορούμε να την φτιάξουμε μόνοι μας χρησιμοποιώντας τις υπόλοιπες λειτουργίες!

Στο ADTMPQ_aux.h module, υπάρχει η παρακάτω συνάρτηση:

// Δημιουργεί και επιστρέφει μια νέα ουρά προτεραιότητας αρχικοποιημένη με τα
// στοιχεία του Vector values.  Τα στοιχεία συγκρίνονται με βάση τη συνάρτηση
// compare.  Αν destroy_value != NULL, τότε καλείται destroy_value(value) κάθε
// φορά που αφαιρείται ένα στοιχείο.

MPQ mpq_create_from_values(CompareFunc compare, DestroyFunc destroy_value, Vector values);

Η συνάρτηση αυτή βρίσκεται εκτός του ADTMPQ.h module, και υλοποιείται χρησιμοποιώντας μόνο το interface του ADT MPQ, χωρίς να γνωρίζει την υλοποίηση. Επίσης, στο αρχείο modules/ADTMPQ_aux.c υπάρχει μια απλοϊκή και αργή υλοποίηση της συνάρτησης, την οποία καλείστε να αντικαταστήσετε με μια πιο αποδοτική, η οποία θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Ο αποδοτικός αλγόριθμος δουλεύει ως εξής:

  • Χωρίζουμε το Vector των δεδομένων σε δύο ίσα τμήματα
  • Δημιουργούμε αναδρομικά MPQ για κάθε τμήμα
    (η αναδρομή τελειώνει όταν ένα τμήμα είναι κενό, οπότε αντιστοιχεί στην κενή ουρά)
  • Και στη συνέχεια συγχωνεύουμε τα δύο MPQ με τη mpq_merge.

Μπορούμε να αποδείξουμε ότι αν η mpq_merge είναι $O(\log n)$, τότε ο παραπάνω αλγόριθμος τρέχει σε $O(n)$. Αναφέρετε στο README.md για ποιες από τις παραπάνω υλοποιήσεις η mpq_create_from_values είναι πραγματικά $O(n)$.

Άσκηση 5 - Υλοποίηση μέσω Binomial Heap (20%)

Ένα Binomial Tree τάξης $k$ ορίζεται αναδρομικά ως εξής:

  • Ένα δέντρο είναι Binomial tree τάξης $0$ αν αποτελείται μόνο από τη ρίζα.
  • Ένα δέντρο είναι Binomial tree τάξης $k$ αν η ρίζα έχει ακριβώς $k$ παιδιά, τα οποία είναι Binomial trees με τάξεις $0,\ldots,k-1$.

Θα αναπαριστούμε έναν κόμβο του Binomial Tree με μία τιμή και ένα Vector από παιδιά, όπου στη θέση $k$ υπάρχει το υπο-δέντρο τάξης $k$.

Ένα Binomial Heap είναι ένα σύνολο από Binomial δέντρα (δάσος), τέτοιο ώστε:

  • Κάθε κόμβος κάθε δέντρου είναι μεγαλύτερος από τα παιδιά του
  • Δεν υπάρχουν δύο δέντρα με την ίδια τάξη

Το δάσος θα το αναπαριστούμε επίσης σαν ένα Vector όπου στη θέση $k$ υπάρχει ένα δέντρο τάξης $k$ (μοναδικό, με βάση τον ορισμό). Ας σημειωθεί ότι σε αντίθεση με τα παιδιά ενός κόμβου, στο δάσος δεν έχουμε αναγκαστικά δέντρα όλων των τάξεων (με άλλα λόγια κάποιες θέσεις του Vector μπορεί να είναι κενές).

Προσθήκη δέντρου στο δάσος. Αν θέλουμε να προσθέσουμε ένα νέο δέντρο τάξης $k$ στο δάσος (θα μας χρειαστεί στη συνέχεια), το κάνουμε ως εξής:

  • Αν η θέση $k$ του Vector είναι κενή, το προσθέτουμε εκεί
  • Αν είναι κατειλημμένη, τότε δεν μπορούμε να έχουμε δύο δέντρα τάξης $k$, οπότε τα συγχωνεύουμε ως εξής:
    • Βρίσκουμε από τα δύο δέντρα αυτό με τη μεγαλύτερη ρίζα.
    • Προσθέτουμε το άλλο δέντρο ως παιδί του πρώτου.
    • Με τη συγχώνευση αυτή, τα δύο δέντρα τάξης $k$ ενώνονται σε ένα τάξης $k+1$, το οποίο αναδρομικά προσθέτουμε στο δάσος.

Merge. Η συγχώνευση δύο Binomial Heaps γίνεται πολύ απλά παίρνοντας ένα-ένα τα δέντρα από το δάσος του δεύτερου, και προσθέτοντάς τα στο δάσος του πρώτου με τον παραπάνω αλγόριθμο. Μπορούμε να αποδείξουμε ότι η λειτουργία αυτή μπορεί να ολοκληρωθεί σε χρόνο $O(\log(n+m))$ όπου $n,m$ τα μεγέθη των δύο Binomial Heaps.

Υπόλοιπες λειτουργίες της ουράς. Έχοντας το merge, όλες οι άλλες λειτουργίες είναι απλές:

  • mpq_max: ελέγχουμε όλα τα δέντρα του δάσους και βρίσκουμε αυτό με τη μεγαλύτερη ρίζα (προαιρετιά μπορούμε και να το έχουμε προ-υπολογίζει).
  • mpq_insert: δημιουργούμε ένα νέο MPQ που περιέχει μόνο τον κόμβο προς εισαγωγή, και το κάνουμε merge στο αρχικό MPQ.
  • mpq_remove_max: βρίσκουμε το δέντρο του δάσους με τη μεγαλύτερη ρίζα, η ρίζα αφαιρείται και τα παιδιά της τα προσθέτουμε στο δάσος με τον παραπάνω αλγόριθμο.

Στο αρχείο modules/UsingBinomialHeap/ADTMPQ.c υπάρχει η δομή της υλοποίησης την οποία καλείστε να επεκτείνετε. Η υλοποίησή σας θα πρέπει να περνάει το υπάρχον test χωρίς leaks.

Bonus (10%)

Προσθέστε μια υλοποίηση του ADT MPQ μέσω Fibonacci Heap, που κάνει το merge ακόμα πιο αποδοτικό.