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.