Τι είναι μια στοίβα στο πλαίσιο του προγραμματισμού και ποιοι τύποι στοίβας υπάρχουν;

Ο σωρός (Heap) είναι μια περιοχή στη μνήμη RAM που χρησιμοποιείται για δυναμική κατανομή μνήμης κατά την εκτέλεση του προγράμματος.

Βασικά χαρακτηριστικά:

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

Τύποι σωρών (στο πλαίσιο δομών δεδομένων):

• Δυαδικός σωρός (Binary Heap): Δέντρο που ικανοποιεί την ιδιότητα του σωρού. Για κάθε κόμβο (εκτός της ρίζας), η τιμή του είναι μικρότερη ή μεγαλύτερη από την τιμή του γονέα.
  • Min Heap: Η τιμή του γονέα είναι πάντα μικρότερη ή ίση με τις τιμές των παιδιών. Το ελάχιστο στοιχείο βρίσκεται στη ρίζα.
  • Max Heap: Η τιμή του γονέα είναι πάντα μεγαλύτερη ή ίση με τις τιμές των παιδιών. Το μέγιστο στοιχείο βρίσκεται στη ρίζα.
• Binomial Heap: Συλλογή binomial δέντρων που ικανοποιούν ορισμένες ιδιότητες. Υποστηρίζει αποτελεσματικές λειτουργίες συγχώνευσης.
• Fibonacci Heap: Δομή δεδομένων που χρησιμοποιείται σε αλγόριθμους όπως ο αλγόριθμος του Dijkstra. Παρέχει πιο αποδοτικούς μέσους χρόνους για ορισμένες λειτουργίες σε σύγκριση με τον δυαδικό σωρό.
• Pairing Heap: Απλή δομή δεδομένων με καλούς μέσους χρόνους.
• Leftist Heap: Δομή δεδομένων που διευκολύνει την αποτελεσματική συγχώνευση. Μια σημαντική ιδιότητα είναι το "βαθμός" ή "μήκος μηδενικής διαδρομής", που χρησιμοποιείται για γρήγορη ένωση.

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