www.pudn.com > heapsort.zip > Lista.cpp

#include "lista.h" 
 
CLista::CLista() { 
	 
	n = 10; 
	array = new int[n+1]; 
} 
 
CLista::CLista(int elementos) { 
	 
	n = elementos; 
	array = new int[n+1]; 
} 
 
void CLista::Insertar() { 
	for (int i=1; i <= n; i++) { 
		cout << "\nDigite un entero: / Integer number " << i << " : "; 
		cin >> array[i]; 
	} 
} 
 
void CLista::Imprimir_Array() { 
	 
	for (int i=1; i <= n; i++) { 
		cout << array[i] << " "; 
	}  
} 
 
void CLista::Intercambia(int a, int b) { 
	 
	int temp; 
	temp = array[a];	// Protege valor de array[a]. 
	array[a] = array[b]; 
	array[b] = temp; 
} 
 
void CLista::Empuja(int primero, int ultimo) { 
	 
	int r = primero;	// Indica la posición actual de array[primero]. 
 
	while (r <= (ultimo/2))  
	{	 
		if (ultimo == (2*r))  // r tiene un hijo en 2*r. 
		{ 
			if(array[r] > array[2*r]) { 
			   Intercambia(r, 2*r);  
			}			 
			r = ultimo;	// Fuerza la terminación del while.			 
		}	 
		else  // r tiene dos hijos, los elementos ubicados en 2*r y 2*r+1 
			if (array[r] > array[2*r] && array[2*r] <= array[2*r+1])  
			{ 
				// intercambia r con su hijo izquierdo. 
				Intercambia(r, 2*r); 
				r = 2*r; 
			} 
		else  
			if(array[r] > array[2*r+1] && array[2*r+1] < array[2*r])  
			{ 
				// intercambia r con su hijo derecho. 
				Intercambia(r, 2*r+1); 
				r = 2*r+1; 
			} 
		else {	// no viola la propiedad de árbol parcialmente ordenado. 
			r = ultimo;	// para forzar la terminación del ciclo while. 
		} 
	} 
}	// Empuja(): 
 
void CLista::HeapSort() { 
// Clasifica el arreglo A[1], ..., A[n] en orden decreciente.	 
 
	int i;	// Cursor hacia array. 
	 
	// Establece inicialmente la propiedad de árbol parcialmente ordenado. 
	for (i = (n/2); i != 0; i--) { 
		Empuja(i, n); 
	} 
	for (i=n; i != 1; i--) { 
		Intercambia(1, i); 
		// Elimina el mínimo del frente del montículo. 
		Empuja(1, i-1); 
		// Restablece la propiedad de árbol parcialmente ordenado. 
	} 
} // HeapSort().