HEAP1 - Một chút về Huffman Tree

Tác giả: RR

Ngôn ngữ: Pascal

var
  u,v,hsize,test,n,i:longint;
  h:array[1..20111] of longint;
  res:int64;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure down(i:longint);
    var
      j:longint;
    begin
      j:=i shl 1;
      while (j<=hsize) do
        begin
          if (j<hsize) and (h[j+1]<h[j]) then inc(j);
          if h[j]<h[i] then
            begin
              swap(h[i],h[j]);
              i:=j; j:=i shl 1;
            end
          else exit;
        end;
    end;

procedure up(i:longint);
    var
      j:longint;
    begin
      j:=i shr 1;
      while (i>1) and (h[i]<h[j]) do
        begin
          swap(h[i],h[j]);
          i:=j; j:=i shr 1;
        end;
    end;

procedure push(u:longint);
    begin
      inc(hsize); h[hsize]:=u;
      up(hsize);
    end;

procedure pop(var u:longint);
    begin
      u:=h[1];
      swap(h[1],h[hsize]);
      dec(hsize); down(1);
    end;

begin
  read(test);
  for test:=1 to test do
    begin
      read(n); for i:=1 to n do begin read(u); push(u); end;
      res:=0;
      while hsize>1 do
        begin
          pop(u); pop(v);
          res:=res+u+v;
          push(u+v);
        end;

      pop(u);
      writeln(res);
    end;
end.

Download