Τι είναι μια στοίβα (στο πλαίσιο των δομών…

Ένα σωρό (heap) είναι ένα εξειδικευμένο δέντρο που χρησιμοποιείται ως δομή δεδομένων. Η βασική ιδιότητα του σωρού είναι η μερική ταξινόμηση: για κάθε κορυφή, η συνθήκη είναι ότι η τιμή της γονικής κορυφής είναι μεγαλύτερη ή ίση με την τιμή οποιουδήποτε από τα παιδιά της (max-heap) ή μικρότερη ή ίση (min-heap).

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

Δυαδικό δέντρο: Συνήθως υλοποιείται ως δυαδικό δέντρο, όπου κάθε κόμβος έχει το πολύ δύο απογόνους.
Πλήρες δυαδικό δέντρο: Σε όλα τα επίπεδα, εκτός ίσως από το τελευταίο, το δέντρο είναι πλήρως γεμάτο. Οι κόμβοι στο τελευταίο επίπεδο γεμίζουν από αριστερά προς τα δεξιά. Αυτό επιτρέπει την αποδοτική αποθήκευση του σωρού σε μορφή πίνακα.
Ιδιότητα του σωρού:
- Max-heap: Η τιμή κάθε κόμβου είναι μεγαλύτερη ή ίση με τις τιμές των απογόνων του. Το μέγιστο στοιχείο βρίσκεται πάντα στην κορυφή.
- Min-heap: Η τιμή κάθε κόμβου είναι μικρότερη ή ίση με τις τιμές των απογόνων του. Το ελάχιστο στοιχείο βρίσκεται πάντα στην κορυφή.

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

Εισαγωγή στοιχείου: Προσθήκη ενός νέου στοιχείου και διατήρηση της ιδιότητας του σωρού.
Διαγραφή στοιχείου: Διαγραφή του ριζικού στοιχείου (μέγιστο ή ελάχιστο, ανάλογα με τον τύπο του σωρού) και διατήρηση της ιδιότητας του σωρού.
Δημιουργία σωρού: Κατασκευή σωρού από έναν πίνακα στοιχείων.

Εφαρμογές του σωρού:

Ταξινόμηση: Αλγόριθμος ταξινόμησης με σωρό (Heapsort).
Προτεραιότητες ουρές: Αποτελεσματική υλοποίηση ουρών όπου τα στοιχεία επεξεργάζονται με βάση την προτεραιότητα.
Αλγόριθμοι αναζήτησης: Για παράδειγμα, αναζήτηση του k-ου μεγαλύτερου στοιχείου.
Αλγόριθμοι σε γράφους: Για παράδειγμα, ο αλγόριθμος Dijkstra.

Απεικόνιση του σωρού σε πίνακα:

Επειδή ο σωρός είναι πλήρες δυαδικό δέντρο, μπορεί να αποθηκευτεί αποτελεσματικά σε πίνακα χωρίς δείκτες.

Αν ένας κόμβος βρίσκεται στη θέση i, ο αριστερός του απογόνος βρίσκεται στη θέση 2*i + 1.
Ο δεξιός του απογόνος βρίσκεται στη θέση 2*i + 2.
Ο γονέας του βρίσκεται στη θέση (i - 1) / 2.

# Παράδειγμα αναπαράστασης ενός min-heap ως πίνακας
heap_array = [10, 15, 20, 17, 25, 30]

# Ρίζα: heap_array[0] = 10
# Αριστερός απογόνος της ρίζας: heap_array[2*0 + 1] = heap_array[1] = 15
# Δεξιός απογόνος της ρίζας: heap_array[2*0 + 2] = heap_array[2] = 20
# Γονέας του στοιχείου στη θέση 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15

Τι είναι μια στοίβα (στο πλαίσιο των δομών δεδομένων);