Recursive implementation of Heap sort algorithm

L’ heapsort è un algoritmo di ordinamento iterativo ed in-place proposto da Williams nel 1964, che si basa su strutture dati ausiliarie.

L’ heapsort per eseguire l’ordinamento, utilizza una struttura chiamata heap (mucchio); un heap è rappresentabile con un albero binario in cui tutti i nodi seguono una data proprietà, detta priorità. Esso è completo almeno fino al penultimo livello dell’albero e ad ogni nodo corrisponde uno ed un solo elemento.

In uno heap decrescente (utilizzato per ordinare ad esempio un array in senso crescente) ogni nodo padre contiene un valore maggiore o uguale a quello dei suoi due figli diretti, di conseguenza risulterà maggiore anche di tutti i nodi che si trovano nel sottoalbero di cui esso è la radice; questo non implica affatto che nodi a profondità maggiore contengano valori minori di quelli a profondità minore.

Quindi in ogni istante, in un heap decrescente, la radice contiene il valore maggiore.

Questa struttura è molto usata, in particolare, per l’ordinamento di array.

In questo caso si considera come radice l’elemento iniziale di indice 1; inoltre i figli di un nodo con indice j, avranno indice rispettivamente 2j, quello sinistro, 2j+1 quello destro.

Continue reading “Recursive implementation of Heap sort algorithm”

C implementation of Heap sort algorithm

L’ heapsort è un algoritmo di ordinamento iterativo ed in-place proposto da Williams nel 1964, che si basa su strutture dati ausiliarie.

L’ heapsort per eseguire l’ordinamento, utilizza una struttura chiamata heap (mucchio); un heap è rappresentabile con un albero binario in cui tutti i nodi seguono una data proprietà, detta priorità. Esso è completo almeno fino al penultimo livello dell’albero e ad ogni nodo corrisponde uno ed un solo elemento.

In uno heap decrescente (utilizzato per ordinare ad esempio un array in senso crescente) ogni nodo padre contiene un valore maggiore o uguale a quello dei suoi due figli diretti, di conseguenza risulterà maggiore anche di tutti i nodi che si trovano nel sottoalbero di cui esso è la radice; questo non implica affatto che nodi a profondità maggiore contengano valori minori di quelli a profondità minore.

Quindi in ogni istante, in un heap decrescente, la radice contiene il valore maggiore.

Questa struttura è molto usata, in particolare, per l’ordinamento di array.

In questo caso si considera come radice l’elemento iniziale di indice 1; inoltre i figli di un nodo con indice j, avranno indice rispettivamente 2j, quello sinistro, 2j+1 quello destro.

Continue reading “C implementation of Heap sort algorithm”