Heap sort

Basandoci sul max heap binario, si può creare un algoritmo di sorting. Nel max heap binario si ha il valore più alto memorizzato nella radice, e nell’array il valore massimo va memorizzato in H[dim(H)].

HeapSort(H):
	costruisciHeap(H)
	for i = H.length-1 downto 1
		H[i] := estrazioneMassimoHeap(H)

Il costo computazionale di questo algoritmo è $O(n\log n)$.

asd_22