/*
 * Instituto Superior de Engenharia do Porto
 *
 * Estruturas de Informação
 *
 * 2000/2001
 *
 * (C) Paulo Sousa
 *
 * ------------------------------------------
 *
 * Trabalho nº 1
 *
 *	algoritmo heapsort
 *
 */


/**

  descrição em http://www.people.fas.harvard.edu/~toub/cs50/sorting/heap.html

  O(n log n)

 **/


#ifndef __HEAPSORT_INC__
#define __HEAPSORT_INC__


template <class T>
class HeapSort
{
	static void downheap_1(T A[], int k, int N);

public:
	static void heapsort_1(T A[], int nSize);
};



//----------------------------------------------------------
//
//				I M P L E M E N T A Ç Ã O
//
//----------------------------------------------------------



template <class T>
void HeapSort<T>::heapsort_1(T A[], int nSize)
{
	if (nSize < 2)
		return;

	int N = nSize;

	for (int k = N/2; k > 0; k--)
		downheap_1(A, k, N);

	do {
		troca(A[0], A[N-1]);
		N--;
		downheap_1(A, 1, N);
	} while (N > 1);
}

template <class T>
void HeapSort<T>::downheap_1(T A[], int k, int N) 
{
	T temp = A[k - 1];

	while (k <= N/2) 
	{
		int j = k + k;
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		if ((j < N) && (A[j - 1] < A[j])) 
			j++;

		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		if (temp >= A[j - 1]) 
			break;
		else 
		{
			A[k - 1] = A[j - 1];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			k = j;
		}
	}
	A[k - 1] = temp;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
}




#endif