#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_HEAP_SORT_BASIC
#define CA_UWATERLOO_ALUMNI_DWHARDER_HEAP_SORT_BASIC

namespace Sorting_algorithms {
	namespace Heap_sort {
		class Basic {
			public:
				template <typename Type>
				static void sort( Type *array, int n ) {
					Type *heap = array - 1;
				
					convert_to_max_heap( heap, n );
					convert_to_sorted_array( heap, n );
				}
				
			private:
				template <typename Type>
				static void convert_to_max_heap( Type *heap, int n ) {
					for ( int i = n/2; i >= 1; --i ) {
						percolate_down( heap, i, n );
					}
				}
				
				template <typename Type>
				static void convert_to_sorted_array( Type *heap, int n ) {
					// Create the Sorted Array
					// Dequeue the maximum element and place it into the ith location
					for ( int i = n; i >= 2; --i ) {
						// Swap the first and last entries of the heap
						Type max = heap[1];
						heap[1] = heap[i];
						heap[i] = max;
				
						percolate_down( heap, 1, i - 1 );
					}
				}
				
				template <typename Type>
				static void percolate_down( Type *heap, int posn, int n ) {
					while ( 2*posn + 1 <= n ) {
						if ( heap[2*posn] > heap[2*posn + 1] && heap[2*posn] > heap[posn] ) {
							// The left child is the largest of the current node and its children
							swap_and_update( heap, posn, 2*posn );
						} else if ( heap[2*posn + 1] > heap[posn] ) {
							// The right child is the largest of the current node and its children
							swap_and_update( heap, posn, 2*posn + 1 );
						} else {
							// The current node is larger than either child--stop
							return;
						}
					}
				
					if ( 2*posn == n && heap[2*posn] > heap[posn] ) {
						swap_and_update( heap, posn, 2*posn );
					}
				}
			
				template <typename Type>
				static void swap_and_update( Type *array, int &i, int j ) {
					Type tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
				
					i = j;
				}
		};
	}
}
			
#endif