program FilaPrioridadesMax;
{ Retira o maior elemento do conjunto - usado no Heapsort }

const INFINITO = MAXINT;
      MAXTAM = 20;

type TipoChave  = integer;
     TipoItem   = record 
                    Chave: TipoChave;
                    { outros componentes }
                  end;
     TipoIndice = 0..MAXTAM;
     TipoVetor  = array [TipoIndice] of TipoItem;

var A: TipoVetor;
    B: TipoVetor;
    i: TipoIndice;
    n: TipoIndice;
    x: TipoItem;

procedure Refaz (Esq, Dir: TipoIndice; var A: TipoVetor);
label 999;
var i: TipoIndice;
    j: integer;
    x: TipoItem;
begin
  i := Esq; j := 2 * i;
  x := A[i];
  while j <= Dir do
    begin
    if j < Dir
    then if A[j].Chave < A[j + 1].Chave then j := j + 1;
    if x.Chave >= A[j].Chave then goto 999;
    A[i] := A[j];
    i := j; j := 2 * i;
    end;
  999: A[i] := x;
end; { Refaz }

procedure Constroi (var A: TipoVetor; var n: TipoIndice);
var Esq: TipoIndice;
begin
  Esq := n div 2 + 1;
  while Esq > 1 do
    begin
    Esq := Esq - 1;
    Refaz (Esq, n, A);
    end;
end; { Constroi }

function Max (var A: TipoVetor): TipoItem;
begin
  Max := A[1];
end; { Max }

function RetiraMax (var A: TipoVetor; var n: TipoIndice): TipoItem;
begin
  if n < 1 
  then writeln('Erro: heap vazio')
  else begin
       RetiraMax := A[1];
       A[1] := A[n];
       n := n - 1;
       Refaz (1, n, A);
       end;
end; 

procedure AumentaChave (i: TipoIndice;
                        ChaveNova: TipoChave;
			var A: TipoVetor);
var k: integer;
    x: TipoItem;
begin
  if ChaveNova < A[i].Chave
  then writeln('Erro: ChaveNova menor que a chave atual')
  else begin
       A[i].Chave := ChaveNova;
       while (i>1) and (A[i div 2].Chave < A[i].Chave)
         do begin
            x := A[i div 2]; A[i div 2] := A[i];
            A[i] := x;       i := i div 2;
            end;
       end;
end;

procedure Insere (var x: TipoItem; 
                  var A: TipoVetor; 
		  var n: TipoIndice);
begin
  n := n + 1; A[n] := x;
  A[n].Chave := -INFINITO;
  AumentaChave (n, x.Chave, A);
end;

procedure Imprime (V: TipoVetor; var n: TipoIndice);
begin
  for i := 1 to n do write (V[i].Chave,' ');
  writeln;
end;

begin
  n := 7;
  for i := 1 to n do read(A[i].Chave);
  { Teste: 20 15 18 10 12 9 13 }
  write ('Desordenado: ');
  Imprime (A,n);

  write ('Constroi   : ');
  Constroi (A,n);
  Imprime (A,n);

  write ('Aumenta chavei posicao 6 para 25: ');
  AumentaChave (6, 25, A);
  Imprime (A,n);

  x.Chave := 13;
  write ('Insere', x.Chave:3,': ');
  Insere (x, A, n);
  Imprime (A,n);

  writeln ('Max:', Max(A).Chave:3);

  x := RetiraMax (A,n);
  write ('Retira', x.Chave:3, ': ');
  Imprime (A,n);
end.