Heap Sort

Programación IV. Guía 4

1

Facultad:
Ingeniería
Escuela:
Computación
Asignatura: Programación IV

Tema: Métodos de Ordenamiento. Parte 3.
Objetivos Específicos
•

Identificar la estructura de algunos algoritmos de ordenamiento.

•

Interpretar los algoritmos de ordenamiento en sintaxis de C#.

•

Aplicar el algoritmo de ordenamiento HeapSort.

Materiales y Equipo
• GuíaNúmero 4.
• Computadora con programa Microsoft Visual C#.

Introducción Teórica
Montículos (Heaps).
Un montículo se define como “Para todo nodo del árbol se debe cumplir que su valor es mayor
o igual al de cualquiera de sus hijos”.
Para representar un montículo en un arreglo lineal:
1. El nodo k se almacena en la posición k correspondiente del arreglo.
2. El hijo izquierda del nodo k, sealmacena en la posición 2 * k.
3. El hijo derecho del nodo k, se almacena en la posición 2 * k+1.
La estructura de datos Montículo es un arreglo de objetos que puede ser visto como un árbol
binario con raíz, cuyos nodos pertenecen a un conjunto totalmente ordenado, y tal que cumple
las siguientes dos propiedades:

a) Propiedad de orden: La raíz de cada subárbol es mayor o igual quecualquiera de sus
nodos restantes.

b) Propiedad de forma: La longitud de toda rama es h o h − 1, donde “h” es la altura del
árbol. Además, si una rama termina en una hoja a la derecha de otra hoja, ésta última de
altura h − 1, la primera debe ser de altura h − 1.

2 Programación IV, Guía 4

Utilizamos un array para representar un árbol binario.

Un arreglo A que representa un montículo es unobjeto con 2 atributos:
•

Length [A]: número de elementos en el arreglo.

•

Heap-size[A]: número de elementos en el montículo almacenados dentro de A

Programación IV. Guía 4

3

A[1….heap − size[A]] es el montículo representado.

Método de Ordenamiento HeapSort.
Se toman las mejores características de los dos algoritmos de ordenamiento basados en
comparación (MergeSort eInsertionSort) para crear un nuevo algoritmo llamado HeapSort.
Este algoritmo está basado en la estructura de montículo.
El método de ordenación HeapSort es también conocido con el nombre “montículo” en el
mundo de habla hispana. Su nombre se debe a su autor J. W. Williams quien lo bautizó así.
Es el más eficiente de los métodos de ordenación que trabajan con árboles.
La idea central de estealgoritmo consiste en lo siguiente:
•

Construir un montículo.

•

Eliminar la raíz del montículo en forma repetida.

El método de ordenación se puede describir con los siguientes pasos:
1. Construir un montículo inicial con todos los elementos del vector A[1], A[2], …., A[n]
2. Intercambiar los valores de A[1] y A[n] (siempre se queda el máximo en el extremo)
3. Reconstruir el montículo conlos elementos A[1], A[2],……, A[n-1]
4. Intercambiar los valores de A[1] y A[n-1]
5. Reconstruir el montículo con los elementos A[1], A[2],……, A[n-2]
Este es un proceso iterativo que partiendo de un montículo inicial, repite intercambiar los
extremos, decrementar en 1 la posición del extremo superior y reconstruir el montículo del
nuevo vector.
Lo expresamos en forma algorítmica así:Ordenación Heapsort (Vector, N)
debe construirse un montículo inicial (Vector, N)
desde k = N hasta 2 hacer
intercambio (Vector[1], Vector[k])
construir montículo (Vector, 1, k-1)
fin desde
Entonces de acuerdo al algoritmo debemos considerar dos problemas:
•

Construir el montículo inicial.

•

Cómo restablecer los montículos intermedios.

4 Programación IV, Guía 4
Para restablecer elmontículo hay dos posibilidades:
•

A [1] es menor o igual que los valores de sus hijos, entonces la propiedad del montículo
no se ha roto.

•

En otro caso, el elemento mínimo que necesitamos poner en A [1] es o su hijo izquierdo
o su hijo derecho (A[2], A[3] respectivamente): Por lo que se determina el menor de sus
hijos y éste se intercambia con A[1]. El proceso continúa repitiendo...