Да и по некоторым иным соображениям лучше не экономить нулевой элемент массива. А выравнивать массив на границу пары интов.

const int WindowLength = 1000000;
const int BufferLength = 2 * WindowLength;

int buffer[BufferLength];
int nextIndex = WindowLength;

int shiftWindow( int nextValue )
{
	buffer[nextIndex] = nextValue;

	int node = nextIndex;
	int nodeValue = nextValue;
	while( node > 1 ) {
		int pair = node ^ 1;
		int parent = node >> 1;

		int newParentValue = max( nodeValue, buffer[pair] );
		if( newParentValue == buffer[parent] )
			break;

		buffer[parent] = newParentValue;
		node = parent;
		nodeValue = newParentValue;
	}

	if( ++nextIndex >= BufferLength )
		nextIndex = WindowLength;
	
	return buffer[1];
}