Διωνυμικός σωρός

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

Οι διωνυμικοί σωροί παρουσιάστηκαν από τον Jean Vuillemin το 1978.

Υλοποίηση

Ο διωνυμικός σωρός αποτελείται από μία συλλογή από διωνυμικά δέντρα διαφορετικής τάξης. Το διωνυμικό δέντρο $k$-οστής τάξης αποτελείται από $2^{k}$ στοιχεία.

Διωνυμικά δέντρα για k=0,1,2,3,4.

Μία διωνυμική σωρός με $n$ στοιχεία αποτελείται από $O(\log _{2}n)$ διωνυμικά δέντρα, ένα για κάθε άσσο στην δυαδική αναπαράσταση του $n$. Για παράδειγμα, αν $n=21$ τότε ο διωνυμικός σωρός αποτελείται από τρία δέντρα τάξης $0,2,4$ καθώς στην δυαδική του αναπαράσταση το $21$ είναι $10101_{2}=2^{4}+2^{2}+2^{0}$.

Παράδειγμα διωνυμικού σωρού με $21$ στοιχεία. Αποτελείται από τρία διωνυμικά δέντρα.

Τα στοιχεία σε κάθε διωνυμικό δέντρο είναι διατεταγμένα ώστε να ικανοποιούν την εξής ιδιότητα:

Το στοιχείο ενός κόμβου είναι μικρότερο ή ίσο από όλα τα παιδιά του.

Θα χρησιμοποιήσουμε επιπλέον τις εξής τους ιδιότητες

• Η ένωση δύο διωνυμικών δέντρων ίδιας τάξης μπορεί να γίνει σε $O(1)$ χρόνο. Εισάγουμε το ένα δέντρο με το μεγαλύτερο στοιχείο στη λίστα με τα παιδιά της ρίζας του άλλου δέντρου.
• Η αφαίρεση της ρίζας ενός διωνυμικού δέντρου τάξης $k$ δημιουργεί $k-1$ διωνυμικά δέντρα τάξης $1,2,\ldots ,k-1$.
• Το ύψος ενός διωνυμικού δέντρου τάξης $k$ είναι $k+1$.

Λειτουργίες

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

Λειτουργία	Πολυπλοκότητα
Δημιουργία	$O(\log n)$
Εισαγωγή στοιχείου	$O(\log n)$
Ένωση σωρών	$O(\log n)$
Εύρεση ελάχιστου στοιχείου	$\Theta (1)$
Αφαίρεση ελάχιστου στοιχείου	$O(\log n)$
Μείωση κλειδιού	$O(\log n)$

Ένωση διωνυμικών σωρών

Η ένωση δύο διωνυμικών σωρών με $n_{1}$ και $n_{2}$ στοιχεία αντίστοιχα γίνεται με τρόπο ισομορφικό της πρόσθεσης των αριθμών $n_{1}$ και $n_{2}$ στην δυαδική τους αναπαράσταση. Ξεκινάμε από την μικρότερη τάξη $k=0$ αν έχουν και οι δύο σωροί δέντρο αυτής της τάξης τότε τα ενώνουμε και τα προσθέτουμε με αυτά της πρώτης τάξης. Αν είναι

Η ένωση λοιπόν χρειάζεται το πολύ να διατρέξει μία φορά από όλα τα δέντρα του κάθε σωρού, δηλαδή χρειάζεται $O(\log _{2}n_{1}+\log _{2}n_{2})$ χρόνο.

← Προηγούμενο βήμα ← Προηγούμενο βήμα Επόμενο βήμα → Επόμενο βήμα → 1

Εισαγωγή στοιχείου

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

Επομένως, η εισαγωγή χρειάζεται $O(\log n)$ χρόνο.

Δημιουργία σωρού

Η κατασκευή ενός σωρού με $n$ στοιχεία μπορεί να γίνει με την χρήση $n$ εισαγωγών. Από την παραπάνω ανάλυση, ο χρόνος που χρειάζεται είναι $O(n\log n)$. Η παρακάτω πιο προσκεκτική ανάλυση δείχνει ότι είναι $O(n)$.

Απόδειξη  

Αυτό που θέλουμε να δείξουμε είναι ότι αν έχουμε έναν δυαδικό μετρητή που ξεκινάει από το $0$ και τον αυξήσουμε κατά $1$, $n$ φορές, τότε χρειάζονται το πολύ $O(n)$ αλλαγές.

Για παράδειγμα για $n=8$ έχουμε

${\texttt {000}}+{\texttt {1}}={\texttt {00}}{\underline {\texttt {1}}}$

${\texttt {001}}+{\texttt {1}}={\texttt {0}}{\underline {\texttt {10}}}$

${\texttt {010}}+{\texttt {1}}={\texttt {01}}{\underline {\texttt {1}}}$

${\texttt {011}}+{\texttt {1}}={\texttt {}}{\underline {\texttt {100}}}$

${\texttt {100}}+{\texttt {1}}={\texttt {10}}{\underline {\texttt {1}}}$

${\texttt {101}}+{\texttt {1}}={\texttt {1}}{\underline {\texttt {10}}}$

${\texttt {110}}+{\texttt {1}}={\texttt {11}}{\underline {\texttt {1}}}$

${\texttt {111}}+{\texttt {1}}={\texttt {1}}{\underline {\texttt {000}}}$

Γενικεύοντας το παραπάνω παράδειγμα προκύπτει ότι το ψηφίο στην θέση $i$ αλλάζει κάθε $2^{i}$ αυξήσεις. Επομένως για $n=2^{m}$ συνολικά χρειάζονται

${\frac {2^{m}}{2^{0}}}+{\frac {2^{m}}{2^{1}}}+{\frac {2^{m}}{2^{2}}}+\ldots +{\frac {2^{m}}{2^{m-1}}}=2^{m}+2^{m-1}+\ldots +2^{1}=2^{m+1}-2\leq 2n$.

← Προηγούμενο βήμα ← Προηγούμενο βήμα Επόμενο βήμα → Επόμενο βήμα → 1

Εύρεση ελάχιστου στοιχείου

Για την εύρεση του ελάχιστου στοιχείου αρκεί να κοιτάξουμε τις ρίζες των διωνυμικών δέντρων.

Η ρίζα ενός διωνυμικού δέντρου είναι μικρότερη από κάθε άλλο στοιχείο του δέντρου. Επομένως, το ελάχιστο στοιχείο του σωρού είναι η ρίζα κάποιου από τα διωνυμικά δέντρα. Επομένως, διατρέχοντάς τα $\leq \lceil \log _{2}n\rceil$ διωνυμικά δέντρα, μπορούμε σε $O(\log n)$ χρόνο να εντοπίσουμε το ελάχιστο στοιχείο.

Επίσης, μπορούμε στο τέλος κάθε μίας από τις προηγούμενες πράξεις να ανανεώνουμε το ελάχιστο στοιχείο, και έτσι η εύρεση να γίνεται σε $O(1)$ χρόνο.

Αφαίρεση ελάχιστου στοιχείου

Βρίσκουμε το διωνυμικό δέντρο που περιέχει το ελάχιστο στοιχείο. Έστω ότι είναι ένα δέντρο τάξης $k$. Αφαιρώντας την ρίζα του λαμβάνουμε $k-1$ διωνυμικά δέντρα τάξης $1,2,\ldots ,k-1$. Έπειτα, ενώνουμε την υπολοιπόμενη σωρό με την σωρό που σχηματίζουν τα $k-1$ καινούργια διωνυμικά δέντρα. Αυτή η ένωση μας δίνει μία διωνυμική σωρό με όλα τα στοιχεία εκτός του ελαχίστου.

Γνωρίζουμε ότι $k=O(\log n)$, επομένως η αφαίρεση της ρίζας και η ένωση χρειάζονται συνολικά $O(\log n)$ χρόνο.

← Προηγούμενο βήμα ← Προηγούμενο βήμα Επόμενο βήμα → Επόμενο βήμα → 1

Μείωση κλειδιού

Όταν μειώσουμε ένα στοιχείο, τότε μπορεί να γίνει μικρότερο από τον πατέρα του, επομένως του αλλάζουμε θέση με τον πατέρα του έως ότου να μην ισχύει αυτό. Κάθε δέντρο έχει ύψος $O(\log n)$ άρα μείωση κλειδιού μπορεί να υλοποιηθεί σε $O(\log n)$ χρόνο.

Δείτε επίσης

• Σωρός
• Διωνυμικό δέντρο