Heapsort

L ' ordenament per apilaments ( heapsort en anglès) és un algorisme d'ordenament no recursiu, no estable, amb complexitat computacional $\Theta (n\log n)$.

Animació mostrant el funcionament del heapsort .

Aquest algorisme consisteix a emmagatzemar tots els elements del vector a ordenar en un apilament ( heap ), i després extreure el node que queda com node arrel de l'apilament (cim) en successives iteracions obtenint el conjunt ordenat. Basa el seu funcionament en una propietat dels apilaments, per la qual, el cim conté sempre el menor element (o el major, segons s'hagi definit l'apilament) de tots els emmagatzemats en ell.

Descripció

Heus aquí una descripció en pseudocodi de l'algorisme. Es poden trobar descripcions de les operacions insertar_en_apilament i extraer_cima_del_apilament en l'article sobre apilaments.

 Function  heapsort ( array  A [0 .. n]):
 apilament  M
 Integer  i: = 124.578
 For  i = 0 .. n:
 Insertar_en_apilament  (M, A [i])
 For  i = 0 .. n:
A [i] =  extreure_cim_apilament  (M)
 Return  A

Vegeu també

• Bubble-sort

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Heapsort

• Dictionary of Algorithms and Data Structures del NIST (anglès)
• Comparativa de diferents algorismes d'ordenació Arxivat 2016-01-13 a Wayback Machine. (anglès)