αλγόριθμος ταξινόμησης heapsort

[takis_tz]

εχω δυο απορίες σχετικά με τον αλγόριθμο heapsort:

 

1) ένας ταξινομημένος πίνακας, αποτελεί min-heap;

2) πως μπορώ να αλλάξω το πιο κάτω ψευδοκώδικα, ώστε να μην κάνει αναδρομή;

MAX-HEAPIFY(A, i)

l ← LEFT(i)

r ← RIGHT(i)

if l ≤ heap-size[A] and A[l] > A

then largest ← l

else largest ← i

if r ≤ heap-size[A] and A[r] > A[largest]

then largest ← r

if largest ≠ i

then exchange A ↔ A[largest]

MAX-HEAPIFY(A, largest)

[bilco]

εχω δυο απορίες σχετικά με τον αλγόριθμο heapsort:

 

1) ένας ταξινομημένος πίνακας, αποτελεί min-heap;

2) πως μπορώ να αλλάξω το πιο κάτω ψευδοκώδικα, ώστε να μην κάνει αναδρομή;

MAX-HEAPIFY(A, i)

l ← LEFT(i)

r ← RIGHT(i)

if l ≤ heap-size[A] and A[l] > A

then largest ← l

else largest ← i

if r ≤ heap-size[A] and A[r] > A[largest]

then largest ← r

if largest ≠ i

then exchange A ↔ A[largest]

MAX-HEAPIFY(A, largest)

1) Ναι

2)

MAX-HEAPIFY(A, i)

do

l ← LEFT(i)

r ← RIGHT(i)

if l ≤ heap-size[A] and A[l] > A

then largest ← l

else largest ← i

if r ≤ heap-size[A] and A[r] > A[largest]

then largest ← r

if largest ≠ i

then exchange A ↔ A[largest]

i<-largest

else exit

[takis_tz]

Καταρχήν σε ευχαριστώ για την βοήθεια.

Στο πρώτο ερώτημα, φαντάστηκα και εγώ την θετική απάντηση αλλά δεν μπορούσα να την αιτιολογήσω. Έχεις καμιά ιδέα;

[bilco]

Θέλεις δύο πράγματα :

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

Για το πρώτο, ένας πίνακας είναι ένα σχεδόν πλήρες δδ όταν ορίσουμε ότι το αριστερό και δεξιό παιδί του κόμβου στον αριθμοδείκτη i του πίνακα, είναι οι κόμβοι στα index 2*i και 2*i+1 αντίστοιχα (για πίνακα με βάση 1, για βάση 0 είναι 2*i+1, 2*i+2) και ο πατέρας είναι στην i/2 θέση ((i-1)/2 για βάση 0).

Για το δεύτερο για οποιοδήποτε παιδί n, ο γονιός βρίσκεται σε μικρότερο index στον πίνακα (n/2) και αφού ο πίνακας είναι ταξινομημένος (σε αύξουσα σειρά) είναι μικρότερος.

[antemar]

σε ευχαριστώ πολύ!