HEAP SORT

Proviene del inglés y significa ordenamiento por montículos. Es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O (n log n).

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un stack(heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Descripción

1. Construir un Heap sobre el arreglo a ordenar (BUILD_HEAP), en orden contrario al orden de ordenación. Por ejemplo, para ordenar ascendentemente un arreglo se construye un HEAP sobre él de forma descendiente (el mayor elemento queda en la raíz)
2. Intercambiar la raíz del Heap, posición 0, con la ultima posición en el Heap.
3. Disminuir el tamaño del Heap.
4. Reconstruir el Heap aplicando Heapify en la primera posición.
5. Repetir los pasos 2, 3 y 4 mientras el tamaño del Heap sea mayor que uno.

Complejidad del algoritmo

• La operación (1), BUILD_HEAP, es O(n log n).
• Las operaciones (2) y (3) son O(1).
• La operación (4), HEAPIFY tiene O(log n).
• Las operaciones (2), (3) y (4) se ejecutan n-1 veces por lo que el algoritmo es 0(nlog n).

Pseudocódigo

HEAPSORT( T[ ] A, entero n) { 
 BUILD_HEAP(A, n);           (1) 
 mientras(n > 1) 
 { Intercambiar(A, 0, n- 1); (2) 
   n--;                      (3) 
 HEAPIFY(A, 0, n);           (4) 
 } 
} 

Github

https://github.com/ingenierajessica/Algoritmos/blob/master/Heap%20Sort.ipynb

Conceptos

Árbol binario

Un árbol binario es una estructura de datos de árbol en la que cada nodo padre puede tener como máximo dos hijos.

Propiedades

• Fue el primer algoritmo que surgió de los que ordenan en O(n log n).
• Ordena en el lugar
  • No utiliza memoria auxiliar
• No es Estable

Ejemplos

Material de Apoyo

Algoritmo de ordenamiento: Heap Sort