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髇 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髇 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 醨bol parcialmente ordenado.
			r = ultimo;	// para forzar la terminaci髇 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 醨bol parcialmente ordenado.
	for (i = (n/2); i != 0; i--) {
		Empuja(i, n);
	}
	for (i=n; i != 1; i--) {
		Intercambia(1, i);
		// Elimina el m韓imo del frente del mont韈ulo.
		Empuja(1, i-1);
		// Restablece la propiedad de 醨bol parcialmente ordenado.
	}
} // HeapSort().