HeapSort en C++

Hola amig@s esta vez les traigo otro de los metodos de ordenacion interna en esta ocasion se trata del Heapsort este metodo es el mas eficiente de todos los metodos de ordenacion interna ya que consiste en almacenar todos los elementos del vector de N elementos 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.

La estructura de un monticulo es similar a la de un arbol biario por lo que tendra un nodo padre y 2 nodo hijos en nuestro caso tomaremos nuestro monticulo como maximal esto quiere decir que para construir dicho monticulo  el nodo padre siempre tendra que ser mayor que sus hijos cuando se cumpla dicha condicion extraeremos el nodo raiz (al decir extraer es intercambiar el nodo raiz que se encuentra en la primera posicion del vector por el ultimo de dicho vector) y volveremos a reconstruir el monticulo esta vez con el vector de N-1 y asi sucesivamente hasta que quede completamente ordenado.

Imagen:

Codigo:

Heapsort.cpp

#include"Heapsort.h"
#include<iostream>
using namespace std;
void main(){
 Heapsort h;
 int c;
 cout<<"cuantos datos: ";
 cin>>c;
 for(int i=1;i<=c;i++){
  system("cls");
  cout<<"dato["<<i<<"]: ";
  cin>>h.lista[i];
 }
 system("cls");
 /**/cout<<"Lista Original"<<endl<<endl;
 for(int i=1;i<=c;i++){
  cout<< h.lista[i]<<"  ";
 }
 h.heapsort(h.lista,c);
 cout<<endl;
 cout<<endl<<"Lista Ordenada"<<endl<<endl;
 for(int i=1;i<=c;i++){
  cout<< h.lista[i]<<"  ";
 }cout<<endl<<endl;
 system("pause");
}

Heapsort.h:

#include<iostream>
#include<windows.h>
using namespace std;
#define MAX 100
class Heapsort{
public:
 int lista[MAX]; 
 int j,temp,hijo;
 bool esmonticulo;
 void heapsort(int[] ,int );
 void monticulo(int[] ,int ,int );
};
void Heapsort::monticulo(int lista[],int primero,int ultimo){
 cout<<endl<<endl<<"Nuevo Monticulo"<<endl<<endl;
 esmonticulo=false;
 for(int k=primero; k<=ultimo; k++){
  cout<<lista[k]<<"\t";
 }cout<<endl;
 while((primero<=ultimo/2)&&!esmonticulo){
  if(2*primero==ultimo){
   hijo=2*primero;
  }
  else{
   if(lista[2*primero]>lista[2*primero+1]){
    hijo=2*primero; 
   }else{
    hijo=2*primero+1;
   }
  }if(lista[primero]<lista[hijo]){
   cout<<endl<<endl<<"Cambio de "<<lista[primero]<<" por "<<lista[hijo]<<endl<<endl;
   temp=lista[primero];
   lista[primero]=lista[hijo];
   lista[hijo]=temp;
   primero=hijo;
  }else{
   esmonticulo=true;
  }
 }
}

void Heapsort::heapsort(int lista[],int n){
 for(j=n/2;j>=0;j--){
  monticulo(lista,j,n);
 }
 for(j=n;j>=1;j--){
  temp=lista[0];
  lista[0]=lista[j];
  lista[j]=temp;
  cout<<endl<<"Sacamos al dato "<<lista[j]<<" de la lista."<<endl<<endl;
  cout<<endl<<"************************************************************"<<endl<<"Nueva Lista: "<<endl<<endl;
  for(int k=0; k<j; k++){
  cout<<lista[k]<<"\t";
  }Sleep(2000);cout<<endl;
  monticulo(lista,0,j-1);
 }
 
}

Descarga el código fuente desde aquí: