Heapsort

Ordenar un vector convertint-lo en heap i traient-ne el màxim un cop i un altre.

Conceptes clau

Construcció d'un heap en temps lineal
Heapsort
Cost $\Theta(n \log n)$
Ordenació in situ

Prova-hoHeaps (cua de prioritat)

Al vector, els fills de la posició i són a 2i+1 i 2i+2, i el pare a ⌊(i−1)/2⌋. Cada pare és més petit que els seus fills, així que el mínim és sempre a l'arrel.