Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

σωρός

Σωρός και ουρά προτεραιότητας:

Η ουρά προτεραιότητας είναι ένας αφηρημένος τύπος δεδομένων και ο σωρός είναι μια δομή δεδομένων, επομένως ο σωρός δεν είναι μια ουρά προτεραιότητας.
Υπάρχουν πολλοί τρόποι υλοποίησης ουρών προτεραιότητας, όπως πίνακες και συνδεδεμένες λίστες. Ωστόσο, αυτές οι υλοποιήσεις μπορούν μόνο να εγγυηθούν ότι μία από τις λειτουργίες εισαγωγής και διαγραφής μπορεί να ολοκληρωθεί σε χρονική πολυπλοκότητα O(1)O(1), ενώ η άλλη λειτουργία πρέπει να ολοκληρωθεί σε O(N)O(N) Ολοκληρώθηκε εντός του χρονική πολυπλοκότητα. Ο σωρός μπορεί να επιτρέψει την ολοκλήρωση της λειτουργίας εισαγωγής της ουράς προτεραιότητας εντός της χρονικής πολυπλοκότητας του O(log N)O(logN) και της λειτουργίας διαγραφής να ολοκληρωθεί εντός της χρονικής πολυπλοκότητας του O(log N)O(logN) .

Ένας σωρός είναι ένα ειδικό δυαδικό δέντρο που πληροί τις ακόλουθες προϋποθέσεις:

1. Πλήρες δυαδικό δέντρο (οι κόμβοι τοποθετούνται με τη σειρά από αριστερά προς τα δεξιά).
2. Η τιμή κάθε κόμβου πρέπει να είναι μεγαλύτερη ή ίση ή μικρότερη ή ίση με την τιμή του θυγατρικού του κόμβου.

Χαρακτηριστικά του σωρού:

1. Τα στοιχεία μπορούν να εισαχθούν στο σωρό σε πολυπλοκότητα χρόνου O(logN).
2. Τα στοιχεία μπορούν να διαγραφούν από το σωρό σε πολυπλοκότητα χρόνου O(logN).
3. Η μέγιστη ή η ελάχιστη τιμή στο σωρό μπορεί να ληφθεί εντός χρονικής πολυπλοκότητας O(1).

Ταξινόμηση σωρών:

Μέγιστος σωρός: Η τιμή κάθε κόμβου στο σωρό είναι μεγαλύτερη ή ίση με την τιμή του θυγατρικού του κόμβου. Το επάνω στοιχείο (κόμβος ρίζας) του μέγιστου σωρού είναι η μέγιστη τιμή στο σωρό.
Ελάχιστος σωρός: Η τιμή κάθε κόμβου στο σωρό είναι μικρότερη ή ίση με την τιμή του θυγατρικού του κόμβου. Το επάνω στοιχείο (κόμβος ρίζας) ενός min-heap είναι η ελάχιστη τιμή στο σωρό.
Ο τρέχων αριθμός κόμβου είναι i, ο αριθμός του αριστερού παιδιού είναι 2i και ο αριθμός του δεξιού παιδιού είναι 2i+1.

πολυπλοκότητα χρόνου και πολυπλοκότητα χώρου

Ταξινόμηση σωρών

Θεωρία: Η ταξινόμηση στο σωρό αναφέρεται στη χρήση της δομής δεδομένων του σωρού για την ταξινόμηση ενός συνόλου μη ταξινομημένων στοιχείων.

Τα βήματα του αλγορίθμου ταξινόμησης min-heap είναι τα εξής:

Σωρεύστε όλα τα στοιχεία σε έναν ελάχιστο σωρό.
Αφαιρέστε και διαγράψτε το επάνω στοιχείο του σωρού και τοποθετήστε το επάνω στοιχείο του σωρού στο σύνολο δεδομένων T που αποθηκεύει τα διατεταγμένα στοιχεία.
Αυτή τη στιγμή, ο σωρός θα προσαρμοστεί στο νέο ελάχιστο σωρό.
Επαναλάβετε τα βήματα 3 και 4 μέχρι να μην υπάρχουν στοιχεία στο σωρό.
Σε αυτό το σημείο, προκύπτει ένα νέο σύνολο δεδομένων T, στο οποίο τα στοιχεία είναι διατεταγμένα με σειρά από μικρό σε μεγάλο.

Τα βήματα του αλγόριθμου ταξινόμησης μέγιστου σωρού είναι τα εξής:

Σωρεύστε όλα τα στοιχεία σε ένα μέγιστο σωρό.
Αφαιρέστε και διαγράψτε το επάνω στοιχείο του σωρού και τοποθετήστε το επάνω στοιχείο του σωρού στο σύνολο δεδομένων T που αποθηκεύει τα διατεταγμένα στοιχεία.
Αυτή τη στιγμή, ο σωρός θα προσαρμοστεί στο νέο μέγιστο σωρό.
Επαναλάβετε τα βήματα 3 και 4 μέχρι να μην υπάρχουν στοιχεία στο σωρό.
Σε αυτό το σημείο, λαμβάνεται ένα νέο σύνολο δεδομένων T, στο οποίο τα στοιχεία είναι διατεταγμένα με σειρά από μεγάλο σε μικρό.
Χρονική πολυπλοκότητα: O(Nlog N). N είναι ο αριθμός των στοιχείων στο σωρό.

Πολυπλοκότητα χώρου: O(N). N είναι ο αριθμός των στοιχείων στο σωρό.