Ερώτηση για Heap Tree.

[firewalker]

Έχω ένα άδειο Heap Tree (Max) και έρχονται με την σειρά τα ακόλουθα δεδομένα.

 

50, 73, 23, 72, 10, 30, 27, 7, 36

 

Τα παρακάτω βήματα για την εισαγωγή των δεδομένων είναι σωστά

 

 

ή πρέπει να γεμίσω πρώτα το δέντρο και μετά να γίνει η διάταξη;

 

[V.I.Smirnov]

To ζήτημα είναι στο τέλος να έχεις ένα heap tree με σωστή δομή. Από αυτή την άποψη, το πότε θα αποκατασταθεί η δομή είναι αδιάφορο.

Εξάλλου όταν φτιάχνεις ένα ταξινομημένο δυαδικό δέντρο (ordered binary tree) κάθε κόμβος τίθεται στην σωστή του θέση εξ αρχής, δηλ την στιγμή που προστίθεται.

Πουθενά δεν θυμάμαι να είδα πρώτα να το φτιάχνεις στην τύχη (δηλ. non ordered) και μετά να αποθιστάς την δομή (εκτός από κάποιες περιπτώσεις balancing όπως στα AVL).

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

 

Το ίδιο και στη συγκεκριμένη περίπτωση - μπορείς να το κάνεις και μετά δηλ. αφού γεμίσει το δέντρο.

Πρέπει να γράψεις μια συνάρτηση που κάνει heapifying, δηλ. αποκατάσταση της heap condition.

Στο πρώτο σχήμα που παραθέτεις, ένας νέος κόμβος προστίθεται από κάτω (bottom of the heap).

Δηλ. η δομή είναι τέτοια ώστε η προτεραιότητα κάποιου κόμβου να αυξάνεται προς τα κάτω.

Συνεπώς πρέπει να γράψεις μια συνάρτηση που κάνει bottom-up heapifying (δηλ. σαρώνοντας το δέντρο προς τα πάνω).

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

Αν γράψεις μια συνάρτηση που μπορεί να κάνει bottom-up heapifying εκ των υστέρων δεν θα είναι λάθος αφού στο τέλος θα έχεις την σωστή δομή.

 

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

την εν δυνάμει ανά κόμβο (που μάλλον είναι με μια πρόχειρη σκέψη.)

Γι αυτό και δεν την βλέπουμε πουθενά - εγώ τουλάχιστον ως ερασιτέχνης δεν την έχω δει...

[firewalker]

Καταρχήν σε ευχαριστώ πολύ για την απάντηση.

 

Άρα θεωρείς το πρώτο σχήμα σωστό.

 

Έλεγα μήπως υπάρχει κάποιος κανόνας να γεμίζεις πρώτα το δέντρο (με την σειρά αριστερά προς δεξιά) και μετά να γίνετε το heapify.

[V.I.Smirnov]

Καταρχήν σε ευχαριστώ πολύ για την απάντηση.

 

Άρα θεωρείς το πρώτο σχήμα σωστό.

 

Έλεγα μήπως υπάρχει κάποιος κανόνας να γεμίζεις πρώτα το δέντρο (με την σειρά αριστερά προς δεξιά) και μετά να γίνετε το heapify.

 

Κοίτα, εγώ δεν έχω σπουδάσει πληροφορική. To πρώτο σχήμα είναι σίγουρα σωστό διότι συμφωνεί με την ''κλασσική" δημιουργία του heap tree όπως παρουσιάζεται στην βιβλιογραφία.

Πιστεύω όμως ότι και το δεύτερο είναι εντάξει αν μπορείς στο τέλος να αποκαταστήσεις την σωστή δομή.

Αλλά όπως έγραψα, δεν το έχω δει πουθενά αυτό. Ο Sedgewick στο βιβλίο του "Algorithms" δείχνει πώς γίνεται το botoom-up και top-down heapifying και μετά σχολιάζει :

"The basic fixUp and fixDown operations presented, also allow direct implementation for change priority and remove operations.

To change the priority of an item somewhere in the middle of the heap, we use fixUp to move up the heap if the priority is increased and fixDown if the priority is decreased.

Full implementations of such operations, which refer to specific data items, make sense only if a handle is maintained for each item to that item's place in the data structure..."

 

Από αυτό καταλαβαίνω ότι μπορεί να γίνει και εκ των υστέρων.

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

Π.χ. στο εν λόγω βιβλίο, αυτό που ζητάς το κάνει παρακάτω μόνον για priority και binomial queues και όχι γενικά.

[C6WGMN]

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

την εν δυνάμει ανά κόμβο (που μάλλον είναι με μια πρόχειρη σκέψη.)

Γι αυτό και δεν την βλέπουμε πουθενά - εγώ τουλάχιστον ως ερασιτέχνης δεν την έχω δει...

Είναι και οι δύο O(nlogn) με λογάριθμο του 2. Για κάθε fixed αριθμό στοιχείων δεν έχει σημασεία ποιά τεχνική θα χρησιμοποιήσεις. Ωστόσο, στην εισαγωγή κόμβου η μία είναι O(nlogn) ενώ η άλλη O(logn). Ο λόγος που δεν φένεται είναι επειδή με την υλοποίηση εισαγωγής κόμβου καλύπτεις και την δημιουργία του heap tree, έτσι είναι περιττή.

[epersidi]

Όταν λες ότι "Έχω ένα άδειο Heap Tree (Max)" εννοείται ότι έχεις υλοποιημένο τον ΑΤΔ (Αφηρημένο Τύπο Δεδομένων) του Max Heap Tree και αυτό με τη σειρά του σημαίνει ότι έχεις υλοποιημένες και τις κατάλληλες συναρτήσεις που χρειάζονται για να δουλέψεις με αυτόν, π.χ. για να κάνεις εισαγωγή ή διαγραφή στοιχείων. Η συνάρτηση για την εισαγωγή στοιχείων σε Max Heap Tree εννοείται ότι τοποθετεί τα στοιχεία στην κατάλληλη θέση (δες οποιαδήποτε υλοποίηση θες). Οπότε η όλη συζήτηση κρίνεται άκυρη ...

[bobosss]

μιας και η ασκηση σου ειναι απο το ΕΑΠ και την ξέρω συγκεκριμένα σου λέω πως το πρώτο σχήμα είναι σωστό μιας και απ ότι λέει η άσκηση η ταξινόμιση του δέντρου πρέπει να γίνεται κατα την εισαγωγή του στοιχείου και ανα πάσα στιγμή το δέντρο να είναι ταξινομήμένο

Βέβαια στην υλοποίηση όπως είπαν και τα παιδιά είναι θέμα "γούστου" το πότε θα κάνεις την ταξινόμηση.Έτσι και αλλιως στην ουσία την ίδια πράξη εκτελείς.

[firewalker]

μιας και η ασκηση σου ειναι απο το ΕΑΠ και την ξέρω συγκεκριμένα σου λέω πως το πρώτο σχήμα είναι σωστό μιας και απ ότι λέει η άσκηση η ταξινόμιση του δέντρου πρέπει να γίνεται κατα την εισαγωγή του στοιχείου και ανα πάσα στιγμή το δέντρο να είναι ταξινομήμένο

Βέβαια στην υλοποίηση όπως είπαν και τα παιδιά είναι θέμα "γούστου" το πότε θα κάνεις την ταξινόμηση.Έτσι και αλλιως στην ουσία την ίδια πράξη εκτελείς.

 

Ναι, από εκεί είναι. Βοηθώ έναν φίλο.

 

Δεν έχω το βιβλίο και δεν μπορώ να καταλάβω πως ακριβώς τα θέλουν μόνο από την εκφώνηση. Είναι και λίγο η διατύπωση με την μεταφορά των όρων στα Ελληνικά...

 

Σας ευχαριστώ όλους.

[bobosss]

Και γώ το ίδιο κάνω.

Οντως η κατάσταση με τη μεταφορά των όρων στα ελληνικά είναι γελία.Χάνεις μισή ώρα για να καταλάβεις τι θέλει να πεί ο ποιητής.και που να κάνεις και τον κόπο να ρίξεις μια ματιά στα βιβλία που έχουνε...εκεί θα λίωσεις στα γέλια με τις μεταφράσεις.και δεν βάζουνε και σε μια παρένθεση δίπλα τον αγγλικό όρο να καταλαβαίνουμε.