双有序队列算法——处理哈夫曼K叉树的高效算法

算法介绍：

哈夫曼树的思路及实现众所周知，大部分是用堆来维护和实现，这种思路比较清晰，在K比较小的时候处理较快（具体例子接下来再说），而且编程复杂度不是很高，利于应用。但是，其所用的数据结构是树，是在一个森林中操作。有没有更简单的结构？下面介绍一个用一位数组维护的算法——双有序队列算法。

例题分析：

先看一个简单的例子：NOIP2004合并果子

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入文件fruit.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。

输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。                                                                                      思路分析：

很明显，这可以用哈夫曼二叉树解决。拿堆来维护是普遍选择。经过测试，其总耗时为0.02s左右。下面以此为例，介绍一下双有序队列算法的原理和实现。哈夫曼树的思想是贪心，则每次需要取一定量的最小值来处理。普通的排序效率一般都不错，但是会被过大的N给卡住。所以很多人用堆排。堆排虽然处理的较快，但是需要反复维护，可以看做是在反复排序，只是代价很小罢了。有没有可以一劳永逸的算法？有！用归并排序实现，只排一遍.开两个数组，将第一次拍好的数放进去，记录好每个数组的长度和头部位置，然后，进行贪心，从两个队列中选取2个（或K个）最小值，记录消耗，进行合并，放到第二个队列尾部，分别处理每个数组的长度和头部位置。以此类推……直到只剩下一个元素为止即可。证明太简单，略掉。

代码讲解：

核心伪代码：

一.取数阶段：

  q:=;
w:=;    // q，w为记录的每个队列取了几个元素，d为两个队列，位存放的是长度，t1，t2为队列头元素位置

while (q+w<) and (q<d[,]) and (w<d[,]) do            //在判断取够了没有 的同时，也要判断是否溢出
if d[,q+t1+]<=d[,w+t2+] then inc(q) else inc(w);       //     进行贪心选择取数

if q=d[,] then if q+w< then w:=w+(-q);
if w=d[,] then if q+w< then q:=q+(-w);              //   如果因溢出而跳出，补上是很有必要的

取数部分

二.处理阶段（队列为空的转移）：

if d[,]= then begin             //    要保证第一个队列不能为空，第一个是主队列，第二个可以理解为暂存的队列 

for i:=t2+ to d[,]+t2 do
begin
d[,i-t2]:=d[,i];
d[,i]:=;
end;
 d[,]:=d[,];
d[,]:=;
t1:=; t2:=;
end;                                  //    具体的转移不再解释，总之要清理干净

处理阶段

三.计算阶段：

d[,]:=d[,]-q; // 去掉取走的数
h:=;
for i:=t1+ to t1+q do
begin
h:=h+d[,i];
d[,i]:=;
end;
for i:=t2+ to t2+w do
begin
h:=h+d[,i];
d[,i]:=;
end; // 将总和累积起来
ans:=ans+h;
d[,d[,]+t2+]:=h; // 将新出现的元素存放好
d[,]:=d[,]+-w; // 处理长度
t1:=t1+q;
t2:=t2+w; // 处理指针

计算阶段

完整代码

program zht;
var
i,n,h,q,w,t1,t2:longint;
ans:int64;
d:array[..,..] of longint;
a,a2:array[..] of longint;
procedure gb(low,high:longint);
var
q,w,e,mid,k:longint;
begin
if low=high then exit;
mid:=(low+high) div ;
gb(low,mid);
gb(mid+,high);
q:=low;
w:=mid+;
e:=low;
while (q<=mid) and (w<=high) do
if a[q]<a[w] then
 begin
 a2[e]:=a[q];
 inc(e);
 inc(q);
 end else
  begin
  a2[e]:=a[w];
  inc(e);
  inc(w);
  end;

if q<=mid then
 while q<=mid do
 begin
 a2[e]:=a[q];
 inc(e);
 inc(q);
 end else
 while w<=high do
 begin
 a2[e]:=a[w];
 inc(e);
 inc(w);
 end;

for k:=low to high do
a[k]:=a2[k];

end;

begin

readln(n);
for i:= to n do
read(a[i]);
gb(,n);

for i:= to n do
d[,i]:=a[i];
d[,]:=n;

while (d[,]+d[,]<>) do
begin
if d[,]= then begin
 for i:=t2+ to d[,]+t2 do
 begin
 d[,i-t2]:=d[,i];
 d[,i]:=;
 end;

 d[,]:=d[,];
 d[,]:=;
 t1:=; t2:=;
 end;

q:=;
w:=;

while (q+w<) and (q<d[,]) and (w<d[,]) do
if d[,q+t1+]<=d[,w+t2+] then inc(q) else inc(w);

if q=d[,] then if q+w< then w:=w+(-q);
if w=d[,] then if q+w< then q:=q+(-w);

d[,]:=d[,]-q;

h:=;

for i:=t1+ to t1+q do
begin
h:=h+d[,i];
d[,i]:=;
end;

for i:=t2+ to t2+w do
begin
h:=h+d[,i];
d[,i]:=;
end;

ans:=ans+h;

d[,d[,]+t2+]:=h;
d[,]:=d[,]+-w;
t1:=t1+q;
t2:=t2+w;

end;

writeln(ans);

end.

AC代码

小结：

用这样的方法来解哈夫曼问题，经过测试，时间同为0.20s左右。等等，不是说更快吗？再看一个例子：NOI2015荷马史诗

题目描述

追逐影子的人，自己就是影子 ——荷马
    
Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》 组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。
  
一部《荷马史诗》中有n种不同的单词，从1到n进行编号。其中第i种单 词出现的总次数为wi。Allison 想要用k进制串si来替换第i种单词，使得其满足如下要求：
对于任意的 1 ≤ i, j ≤ n ， i ≠ j ，都有：si不是sj的前缀。
现在 Allison 想要知道，如何选择si，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的si的最短长度是多少？
一个字符串被称为k进制字符串，当且仅当它的每个字符是 0 到 k − 1 之间（包括 0 和 k − 1 ）的整数。
字符串 str1 被称为字符串 str2 的前缀，当且仅当：存在 1 ≤ t ≤ m ，使得str1 = str2[1..t]。其中，m是字符串str2的长度，str2[1..t] 表示str2的前t个字符组成的字符串。

算法改进：

样例就不在给出了，直接分析吧。还是同样的思路，再开一个记录类型，w表示长度，m表示深度，然后同样的方法，第一问很好解决，但是要考虑最小深度，这个算法是否可以解决？可以！（读者自己思考证明）其中有个细节必须注意：

if d[1,q+t1+1].w<=d[2,w+t2+1].w then inc(q) else inc(w);

这个等于号相当的重要，在权值相同时，必须优先取第一队列的，因为题目要求在总和最小情况下深度最小，而深度的转移是合并时各个元素的深度的最大值加一，在权值相等情况下，第一队列深度恒小于第二队列深度（有趣的问题当然要自己证明），若不加“=”，只有70分到手（测试过的），一半的点只能拿第一问的分数，所以很不理想，“=”是必不可少的。

时间复杂度为$O(NlogN+2*(N div K)*K)$,在这时，这个算法的优势完全暴露了出来，总用时0.5s，而同等Pascal用堆写2.1S左右，速度为堆的4倍！！！而C++最快的为0.4s左右，基本持平（虽然代码长了点）。因为前面有过框架，就不在就代码给出分析了，认真阅读一下补充数的阶段，进行处理的这几部分，体会和上一题的不同之处。附上代码：

program zht;

type
 z=record
  w:int64;
  m:longint;
  end;

var
i,n,p,m,t1,t2,q,w,k:longint;
a,a2:array[..] of int64;
ans1,ans2,h:int64;
d:array[..,..] of z;

procedure gb(low,high:longint);
var
q,w,e,mid,k:longint;
begin
if low=high then exit;
mid:=(low+high) div ;
gb(low,mid);
gb(mid+,high);
q:=low;
w:=mid+;
e:=low;

while (q<=mid) and (w<=high) do
if a[q]<a[w] then
 begin
 a2[e]:=a[q];
 inc(e);
 inc(q);
 end else
  begin
  a2[e]:=a[w];
  inc(e);
  inc(w);
  end;

if q<=mid then
 while q<=mid do
 begin
 a2[e]:=a[q];
 inc(e);
 inc(q);
 end else
 while w<=high do
 begin
 a2[e]:=a[w];
 inc(e);
 inc(w);
 end;

for k:=low to high do
a[k]:=a2[k];

end;

begin
assign(input,'epic.in');
assign(output,'epic.out');
reset(input);
rewrite(output);

readln(n,k);

for i:= to n do
read(a[i]);

p:=n;

while (p-) mod (k-)<> do
inc(p);

gb(,p);

for i:= to p do
begin
d[,i].w:=a[i];
if a[i]= then d[,i].m:=-maxlongint;
end;

d[,].w:=p;

while d[,].w+d[,].w<> do
begin

if d[,].w= then begin

 for i:=t2+ to t2+d[,].w do
 begin
 d[,i-t2].w:=d[,i].w;
 d[,i-t2].m:=d[,i].m;
 d[,i].w:=; d[,i].m:=;
 end;
  d[,].w:=d[,].w;
  d[,].w:=;
  t1:=; t2:=;
   end;                                                  // zhuan yi

q:=;
w:=;

while (q+w<>k) and (q<d[,].w) and (w<d[,].w) do
if d[,q+t1+].w<=d[,w+t2+].w then inc(q) else inc(w);

if q+w<>k then if q=d[,].w then  w:=w+(k-q-w) else q:=q+(k-w-q);    // qu shu

d[,].w:=d[,].w-q;

m:=;
d[,d[,].w+t2+].w:=ans1;

for i:=t1+ to t1+q do
begin
ans1:=ans1+d[,i].w;
d[,i].w:=;
if d[,i].m>m then m:=d[,i].m;
d[,i].m:=;
end;

for i:=t2+ to t2+w do
begin
ans1:=ans1+d[,i].w;
d[,i].w:=;
if d[,i].m>m then m:=d[,i].m;
d[,i].m:=;
end;

d[,d[,].w+t2+].w:=ans1-d[,d[,].w+t2+].w;
d[,d[,].w+t2+].m:=m+;

d[,].w:=d[,].w-w+;
t1:=t1+q;
t2:=t2+w;

end;

writeln(ans1);
writeln(m+);
close(input);
close(output);
end.

AC代码

总结

根据以上的分析，这种算法大大提高了运算速度，在数据比较大时，远远超过了堆。所以，这是一个优秀的解决哈夫曼树问题的算法。（算法为本人原创，严禁抄袭）