Heap build

Αλγόριθμος Συμπλήρωσης σωρού(σ.σ)

Αλγόριθμος σ.σ(r,n) Είσοδος: Αναπαράσταση δομής σωρού μέσω πίνακα L με δείκτη ρίζας τον r, με N στοιχεία, όπου κάθε ένα από τα υποδέντρα της ρίζας είναι σωρός. Έξοδος: Ίδιο δέντρο, τώρα σωρός Ο αλγόριθμος αυτός μετατρέπει ένα υποδέντρο σε σωρό. Για να εφαρμοστεί όμως θα πρέπει τα παιδιά ( ένα ή δύο υποδέντρα) της ρίζας του υποδέντρου να αποτελούν σωρό, να έχουν δηλαδή την ιδιότητα του σωρού. Ο αλγόριθμος αυτός ουσιαστικά συμπληρώνει τον σωρό μια που τοποθετεί τη ρίζα r του υποδέντρου στη σωστή θέση μέσα στο υποδέντρο. Αν αρχικά η ρίζα του υποδέντρου περιέχει τιμή μεγαλύτερη από τα παιδιά της τότε ο αλγόριθμος τερματίζει. Διαφορετικά η ρίζα μετακινείται προς τα κάτω και εναλλάσσεται με τους απογόνους της μέχρι να τοποθετηθεί στη σωστή θέση. Για καλύτερη κατανόηση των αλγορίθμων κ.σ και σ.σ δείτε το Applet.		Ψευδοκώδικας σ.σ(r,N)
		x=L(r) //το x έχει τη Ποσότητα της ρίζας
		rleft=2r //δείκτης προς αριστερό παιδί
		while rleft£N do //όσο το rleft είναι φύλλο
		max=rleft //το max θα πάρει το μεγαλύτερο παιδί
		rright=rleft+1
		if rright£N and L(right)³L(rleft) then max=rright;
		if x<L(max) then do else break //έξοδος από while
		L(r)=L(max) //το μεγαλύτερο παιδί παίρνει
		r=max //τη θέση του πατέρα
		rleft=2max
		end if
		end while
		L(r)=x //η αρχική ποσότητα της ρίζας x πάει στο r

Αλγόριθμος Συμπλήρωσης σωρού(σ.σ)