//================================ Heap Sort =================================//

template <class TYPE>
void CSort<TYPE>::HeapSort(TYPE data[], int size)
{
	// initialize member variables
	strcpy_s(m_methodName, "Heap Sort");
	m_comparisions = m_movements = 0;
	m_dataSize = size;

	// no point in sorting if there is less than 2 elements
	if (size < 2) return;

	// as long as there are elements
	while(size > 0 )
	{
		// make a heap of the array
		Heapify(data, size);
		size--;

		// put the first (largest) element in the correct place
		swap(data[0], data[size]);
		m_movements++;
	}
}

// funtion to rearrange the heap to maintain the heap property:
// largest element at data[0], child elements less or equal
template <class TYPE>
void CSort<TYPE>::Heapify(TYPE data[], int size)
{
	// loop through the array
	for (int child=0; child<size; child++)
	{
		// 
		int parent = (child - 1) / 2;
		
		while (parent >= 0)
		{
			// if the child is larger than the parent
			if (++m_comparisions, data[child] > data[parent])
			{
				// swap them
				swap(data[parent], data[child]);
				m_movements++;
				// the child is now the parent
				child = parent;
				// 
				parent = parent / 2;
			}
			else
				break;
		}
	}
}