binary heap

[voulaji]

Που μπορω να βρω πληροφοριες για το πως κατασκευάζεται ένας δυαδικός σωρός;

Για παράδειγμα έχω κάποιες τιμές 26, 58, 22,39, 55, 62, 8, 71 & 14. Πως μπορώ να κατασκευάσω έναν max binary heap εάν εισάγω τις τιμές μια κάθε φορά σύμφωνα με την πιο πάνω σειρά;

[aeikinitos]

Δοκίμασε εδώ :

http://en.wikipedia.org/wiki/Binary_heap#Adding_to_the_heap

Το wiki είναι θεός. το 50% τον ασκήσεων μου βρίσκονται εκεί.

[voulaji]

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

[panosrap]

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

 

αυτο ζητάς νομίζω:

(εβαλα τις τελειες για να τα εμφανισει σωστα...)

....70

..../ \

....63 54

..../ \ / \

....59 38 21 8

..../ \

....27 15

 

1.Μετά την εισαγωγή του 27 γίνεται αλλαγή με το 59

2.Με την εισαγωγή του 38 γίνεται αλλαγή με το 27

3.Το 54 αλλάζει με το 21

4.Το 63 αλλαζει με το 38 και στη συνέχεια με το 59

5.Το 70 αλλάζει διαδοχικά με το 2, 59 και 63 και καταλήγει στην κορυφή.

[voulaji]

Δε κατάλαβα την κατασκευή του δέντρου. Έχω φτιάξει κατι διαφορετικό. Μπορείς να το δεις στα συνημμένα και να μου πεις που έχω κάνει λάθος;

[voulaji]

το πρώτο δέντρο είναι:

27

/\

21 59

/ /\

8 38 63

\ \ \

15 54 70

και καταλήγω:

70

/ \

21 63

/ /\

15 54 59

\ \ \

15 38 27

[panosrap]

Ακυρη η απάντηση που σου έδωσα στην αρχή...

η σωστή είναι η εξής:

Περνάς τις τιμές μια-μια κάθε φορά και συγκρινεις το 'παιδι' με τον πατέρα οπότε:

βάζεις τον 1ο αριθμο (στην δικη μου περιπτωση)

27

βαζεις τον δευτερο

59

ειναι μεγαλυτερος συνεπως κανεις αλλαγη (swap)

....59

.../

..27

συνεχίζεις την ιδια διαδικασία κανοντας τις αλλαγές όταν χρειάζεται και γεμίζοντας τον σωρό απο ΑΡΙΣΤΕΡΑ προς τα ΔΕΞΙΑ (το βαζω με κεφαλαια γιατι εκανα λαθος στην προηγουμενη απαντηση που σου εδωσα...)

το τελικο δένδρο θα γίνει

 

. . . . . . . . . . . . . .70

. . . . . . . . . 63. . . . . . . .59

. . . . . .54. . . . .38. . . .21. . .8

. . . .27. . .15

 

οι τιμές καθε υποδενδρου ειναι μικρότερες απο την τιμή του 'πατερα' τους....

Ρίξε μια ματιά και πες μου αν εχεις διαφορετικη αποψη.

Και εγω ειμαι νέος στα πραγματα...

 

Με τις αλλες ασκησεις εκανες κατι?? Την 3 συγκεκριμένα.

[panosrap]

Ακυρη η απάντηση που σου έδωσα στην αρχή...

η σωστή είναι η εξής:

Περνάς τις τιμές μια-μια κάθε φορά και συγκρινεις το 'παιδι' με τον πατέρα οπότε:

βάζεις τον 1ο αριθμο (στην δικη μου περιπτωση)

27

βαζεις τον δευτερο

59

ειναι μεγαλυτερος συνεπως κανεις αλλαγη (swap)

....59

.../

..27

συνεχίζεις την ιδια διαδικασία κανοντας τις αλλαγές όταν χρειάζεται και γεμίζοντας τον σωρό απο ΑΡΙΣΤΕΡΑ προς τα ΔΕΞΙΑ (το βαζω με κεφαλαια γιατι εκανα λαθος στην προηγουμενη απαντηση που σου εδωσα...)

το τελικο δένδρο θα γίνει

 

. . . . . . . . . . . . . .70

. . . . . . . . . 63. . . . . . . .59

. . . . . .54. . . . .38. . . .21. . .8

. . . .27. . .15

 

οι τιμές καθε υποδενδρου ειναι μικρότερες απο την τιμή του 'πατερα' τους....

Ρίξε μια ματιά και πες μου αν εχεις διαφορετικη αποψη.

Και εγω ειμαι νέος στα πραγματα...

 

Με τις αλλες ασκησεις εκανες κατι?? Την 3 συγκεκριμένα.

 

Το δένδρο που έκανα για την περίπτωση σου είναι

. . . . . . . . . . . . . .71

. . . . . . . . . 62. . . . . . . .58

. . . . . .55. . . . .39. . . .22. . .8

. . . .26. . .14