Примерно так:
const int WindowLength = 1000000;
const int BufferLength = 2 * WindowLength - 1;
int buffer[BufferLength];
int nextIndex = WindowLength;
int shiftWindow( int nextValue )
{
buffer[nextIndex] = nextValue;
int node = nextIndex + 1;
int nodeValue = nextValue;
while( node > 1 ) {
int pair = node ^ 1;
int parent = node >> 1;
int newParentValue = max( nodeValue, buffer[pair - 1] );
if( newParentValue == buffer[parent - 1] )
break;
buffer[parent - 1] = newParentValue;
node = parent;
nodeValue = newParentValue;
}
if( ++nextIndex >= BufferLength )
nextIndex = WindowLength;
return buffer[0];
}
Ну и не забыть вначале проинициализировать весь буфер значением INT_MIN