Heapsort

Animación mostrando el funcionamiento del heapsort.

El ordenamiento por montículos (heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional $\Theta(n\log n)$

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (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

He aquí una descripción en pseudocódigo del algoritmo. Se pueden encontrar descripciones de las operaciones insertar_en_monticulo y extraer_cima_del_monticulo en el artículo sobre montículos.

function heapsort(array A[0..n]):
  montículo M
  integer i := 124578
  for i = 0..n:
    insertar_en_monticulo(M, A[i])
  for i = 0..n:
    A[i] = extraer_cima_del_monticulo(M)
  return A

Algoritmo HeapSort en C++

#include "HeapSort.h"
#include <iostream>
#include <math.h>
 
using namespace std;
 
HeapSort::HeapSort( int* array, int arraySize )
{
        this->array                     = array;
        this->arraySize                 = arraySize;
}
 
void HeapSort::heapsort()
{
        for (int i=0; i < arraySize; i++)
        {
                this->crearHeap( i );
        }
}
void HeapSort::crearHeap(int desde)
{
        for (int i=desde; i < arraySize; i++)
        {
                int padre = ((i - desde - 1)/2) + desde;
                int j = i;
                while (padre >= desde && this->array[padre] > this->array[j] )
                {
                        int aux = this->array[padre];
                        this->array[padre] = this->array[j];
                        this->array[j] = aux;
 
                        j = padre;
                        padre = ((padre - desde - 1)/2) + desde;
                }
        }
}
 
void HeapSort::DoSort()
{
        this->heapsort();
}
 
void main()
{
int tam = 100;
int * vector = new int[tam];
 
// ......SE CARGA EL VECTOR
 
HeapSort * sort = new HeapSort( vector, tam );
sort->DoSort(); //se ordena el vector
 
}