Τι είναι μια στοίβα;

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

• Μέγιστος σωρός (Max-heap): Η τιμή του κλειδιού κάθε κορυφής δεν είναι μικρότερη από την τιμή των παιδιών της. Το μέγιστο στοιχείο βρίσκεται στη ρίζα.
• Ελάχιστος σωρός (Min-heap): Η τιμή του κλειδιού κάθε κορυφής δεν είναι μεγαλύτερη από την τιμή των παιδιών της. Το ελάχιστο στοιχείο βρίσκεται στη ρίζα.

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

• Για ένα στοιχείο με δείκτη i (ξεκινώντας από 0), το αριστερό παιδί βρίσκεται στη θέση 2i + 1.
• Το δεξί παιδί βρίσκεται στη θέση 2i + 2.
• Ο γονέας βρίσκεται στη θέση floor((i - 1) / 2).

Βασικές λειτουργίες στον σωρό:

• Εισαγωγή (Insert): Προσθήκη ενός νέου στοιχείου. Χρόνος εκτέλεσης O(log n), όπου n είναι ο αριθμός των στοιχείων.
• Εξαγωγή Μέγιστου / Ελάχιστου (Extract-Max / Extract-Min): Διαγραφή και επιστροφή του μέγιστου (σε max-heap) ή ελάχιστου (σε min-heap) στοιχείου. Χρόνος εκτέλεσης O(log n).
• Heapify (Δημιουργία σωρού): Μετατροπή μιας αυθαίρετης λίστας σε σωρό. Χρόνος εκτέλεσης O(n).

Οι σωροί χρησιμοποιούνται σε αλγορίθμους ταξινόμησης (π.χ., heapsort), σε ουρές προτεραιότητας και σε αλγορίθμους εύρεσης των συντομότερων διαδρομών (π.χ., ο αλγόριθμος του Dijkstra).