QBHEAP - Hàng đợi có độ ưu tiên

Tác giả: flashmt

Ngôn ngữ: Pascal

const maxn=15010;
var h,re:array[1..maxn] of longint;
    n,dem:longint;

procedure update(x:longint);
var cha,con:longint;
begin
     inc(n);
     con:=n; cha:=con shr 1;
     while (cha>0) and (h[cha]<x) do
     begin
          h[con]:=h[cha];
          con:=cha;
          cha:=con shr 1;
     end;
     h[con]:=x;
end;

function pop(val:longint):longint;
var cha,con,x:longint;
begin
     while (h[1]=val) and (n>0) do
     begin
          pop:=h[1];
          x:=h[n];
          dec(n);
          cha:=1; con:=2;
          while con<=n do
          begin
               if (con<n) and (h[con+1]>h[con]) then inc(con);
               if x>=h[con] then break;
               h[cha]:=h[con];
               cha:=con;
               con:=cha shl 1;
          end;
          h[cha]:=x;
     end;
end;

procedure pr;
var i,x:longint; c:char;
begin
     while not eof do
     begin
          read(c);
          if c='+' then
          begin
               read(x);
               if n<15000 then update(x);
          end
          else x:=pop(h[1]);
          readln;
     end;
     repeat
           inc(dem);
           re[dem]:=pop(h[1]);
     until n=0;
     writeln(dem);
     for i:=1 to dem do writeln(re[i]);
end;

begin
     pr;
end.

Download