Πίνακας περιεχομένων:
Ορισμός - Τι σημαίνει Heap;
Ένα σωρό, στο πλαίσιο της δομής δεδομένων, είναι μια δομή δεδομένων που βασίζεται σε δέντρο και ικανοποιεί την ιδιότητα σωρού, όπου σε κάθε στοιχείο έχει εκχωρηθεί μια τιμή-κλειδί ή μια στάθμιση. Το κλειδί χαμηλότερης τιμής έχει πάντοτε έναν γονικό κόμβο με κλειδί υψηλότερης τιμής. Αυτό ονομάζεται δομή max-heap, και μεταξύ όλων των κόμβων, ο κόμβος ρίζας έχει το υψηλότερο κλειδί.
Μερικές φορές, μια δομή που βασίζεται σε δέντρα έχει έναν αντιστρεπτό κανόνα δομής, όπου ένα στοιχείο με κλειδί υψηλότερης τιμής έχει πάντα κλειδί χαμηλότερης τιμής ως γονικό κόμβο. Αυτό ονομάζεται δομή min-heap, και μεταξύ όλων των κόμβων, ο κόμβος ρίζας έχει το χαμηλότερο κλειδί.
Η Techopedia εξηγεί το Heap
Δεν υπάρχουν πρακτικοί περιορισμοί στον αριθμό των παιδιών που κάθε κόμβος μπορεί να έχει σε ένα σωρό, παρόλο που κάθε κόμβος συνήθως έχει δύο, το πολύ. Ο σωρός θεωρείται η πιο αποτελεσματική υλοποίηση ενός αφηρημένου τύπου δεδομένων, γνωστού ως ουρά προτεραιότητας. Η εφαρμογή Heap είναι απαραίτητη σε διάφορους αλγόριθμους γραφημάτων (συμπεριλαμβανομένου του αλγορίθμου Dijkstra) καθώς και στον αλγόριθμο διαλογής heapsort.
Οι σωροί έχουν πολλές παραλλαγές που λειτουργούν ως αφηρημένες υλοποιήσεις ουράς προτεραιότητας τύπου δεδομένων με υψηλή απόδοση. Πολλές εφαρμογές, όπως αλγόριθμοι γραφημάτων, απαιτούν την εφαρμογή ουρών προτεραιότητας.
Ένας πίνακας είναι η πιο κοινή μορφή υλοποίησης σωρού, όπου δεν απαιτούνται δείκτες για τη σύνδεση μεταξύ των στοιχείων του.
Οι σωροί εκτελούν πολλαπλές λειτουργίες, όπως:
- Find-max: Αναζητά τον κόμβο του υψηλότερου κλειδιού μεταξύ μιας ομάδας κόμβων
- Find-min: Αναζητά τον κόμβο χαμηλότερου κλειδιού ανάμεσα σε μια ομάδα κόμβων
- Delete-max: Διαγράφει τον κόμβο του υψηλότερου κλειδιού μεταξύ μιας ομάδας κόμβων
- Διαγραφή-min: Διαγράφει τον κόμβο χαμηλότερου κλειδιού μεταξύ μιας ομάδας κόμβων
Οι σωροί περιλαμβάνουν επίσης λειτουργίες που εκτελούν συγχώνευση, εισαγωγή και αλλαγές κλειδιών.
Ο ορισμός αυτός γράφτηκε στο πλαίσιο της Δομής Δεδομένων
