/*
	Name: HeapSort.cpp
	Copyright: Universidad Nacional Abierta
	Author: Cesar A. Rodriguez C.
	Date: 09/10/16 21:11
	Description: Programa para la solución al problema correspondiente al objetivo 6 del Trabajo Practico de la Materia (324) 2016-1
*/

#include <stdlib.h>
#include <iostream>
#include <time.h>

const int MAX = 101;
	  int k;
      int Heapsort[MAX];

// Arbol Parcialmente ordendo
struct Cola_De_Prioridad{

	int contenido[MAX];
	int ult;
};


Cola_De_Prioridad Crea(Cola_De_Prioridad A){
// Inicializamos la estructura de datos

	int k;

	A.ult = 0;
	for(k = 0; k < MAX; k++)
		A.contenido[k] = 0;

	return A;
};


Cola_De_Prioridad Inserta(int x, Cola_De_Prioridad A){
//Inserta un elemento al arbol y lo ordena de menor a mayor

	int i, temp;

	if(A.ult >= MAX)
		printf("\nLa cola esta llena. \n");
	else{
		A.ult = A.ult + 1;
		A.contenido[A.ult] = x;
		i = A.ult;

		while((i > 1) and (A.contenido[i] < A.contenido[i/2])){
			temp = A.contenido[i];
			A.contenido[i] = A.contenido[i/2];
			A.contenido[i/2] = temp;
			i = i/2;
		}
		return A;
	}
};


void Ver(Cola_De_Prioridad A){
// Imprime el contenido del arbol

	int i;

	for(i = 0; i < MAX; i++)
		printf(" A[%d]= %d \n", i, A.contenido[i]);

	printf("\n A.ult = %d ", A.ult);
	printf("\n\n");
}


Cola_De_Prioridad Empuja(Cola_De_Prioridad A, int primero, int ultimo){
// Reestable la propiedad del arbol parcialmente ordenado hundiendo el dato infractor a donde corresponde

	int r, aux;

	r = primero;
	while(r <= (ultimo/2)){
		if(ultimo == 2*r){
			if( A.contenido[r] > A.contenido[2*r]){
				aux = A.contenido[r];
				A.contenido[r] = A.contenido[2*r];
				A.contenido[2*r] = aux;
				r = ultimo;
			}
			else
			r = ultimo;
		}
		else
			if(A.contenido[r] > A.contenido[2*r] and A.contenido[2*r] <= A.contenido[2*r+1]){
				aux = A.contenido[r];
				A.contenido[r] = A.contenido[2*r];
				A.contenido[2*r] = aux;
				r = 2*r;
			}
		else if(A.contenido[r] > A.contenido[2*r+1] and A.contenido[2*r+1] < A.contenido[2*r]){
				aux = A.contenido[r];
				A.contenido[r] = A.contenido[2*r+1];
				A.contenido[2*r+1] = aux;
				r = 2*r+1;
		}
		else
			r = ultimo;
	}
	return A;
}


int main()
{
printf("\n\n");

    Cola_De_Prioridad Arbol;

    // Inicializamos la estructura
	Arbol = Crea(Arbol);

	//Asignamos valores entre 1 y 1000 a la esctructura y la mostramos.
	srand(clock());
    for(k = 0; k < MAX-1; k++)
    	Arbol = Inserta(rand() % 1001, Arbol);

    // Vemos el resultado
    Ver(Arbol);



// Heapsort

	for(k = 0; k < Arbol.ult; k++){
		Heapsort[k]=Arbol.contenido[1];         // Alamcenamos el dato que resulta ser el de menor valor entre todos.
		Arbol.contenido[1] = Arbol.contenido[Arbol.ult-k]; // Reemplazamos la raiz por la hoja mas a la izquierda del ultimo nivel quebrando la propiedad de los arboles parcialmente ordenados
		Arbol.contenido[Arbol.ult-k] = 0;
  		Arbol =  Empuja(Arbol, 1, Arbol.ult-k-1);  // Restablecemos la propiedad del arbol parcialmente ordenado.
 	}

	printf("  El orden es el siguiente: \n\n ");
	for(k = 0; k < Arbol.ult; k++)
		printf(" %d", Heapsort[k]);

printf("\n\n");
printf("\n\n");
system("pause");
return 0;
}