算法介绍：
哈夫曼树的思路及实现众所周知，大部分是用堆来维护和实现，这种思路比较清晰，在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:=0;
w:=0; // q，w为记录的每个队列取了几个元素，d为两个队列，0位存放的是长度，t1，t2为队列头元素位置
while (q+w<2) and (q<d[1,0]) and (w<d[2,0]) do //在判断取够了没有 的同时，也要判断是否溢出
if d[1,q+t1+1]<=d[2,w+t2+1] then inc(q) else inc(w); // 进行贪心选择取数
if q=d[1,0] then if q+w<2 then w:=w+(2-q);
if w=d[2,0] then if q+w<2 then q:=q+(2-w); // 如果因溢出而跳出，补上是很有必要的
二.处理阶段（队列为空的转移）：
if d[1,0]=0 then begin // 要保证第一个队列不能为空，第一个是主队列，第二个可以理解为暂存的队列
for i:=t2+1 to d[2,0]+t2 do
begin
d[1,i-t2]:=d[2,i];
d[2,i]:=0;
end;
d[1,0]:=d[2,0];
d[2,0]:=0;
t1:=0; t2:=0;
end; // 具体的转移不再解释，总之要清理干净
三.计算阶段：
d[1,0]:=d[1,0]-q; // 去掉取走的数
h:=0;
for i:=t1+1 to t1+q do
begin
h:=h+d[1,i];
d[1,i]:=0;
end;
for i:=t2+1 to t2+w do
begin
h:=h+d[2,i];
d[2,i]:=0;
end; // 将总和累积起来
ans:=ans+h;
d[2,d[2,0]+t2+1]:=h; // 将新出现的元素存放好
d[2,0]:=d[2,0]+1-w; // 处理长度
t1:=t1+q;
t2:=t2+w; // 处理指针
完整代码
program zht;
var
i,n,h,q,w,t1,t2:longint;
ans:int64;
d:array[1..2,0..20000] of longint;
a,a2:array[0..10000] of longint;
procedure gb(low,high:longint);
var
q,w,e,mid,k:longint;
begin
if low=high then exit;
mid:=(low+high) div 2;
gb(low,mid);
gb(mid+1,high);
q:=low;
w:=mid+1;
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:=1 to n do
read(a[i]);
gb(1,n);
for i:=1 to n do
d[1,i]:=a[i];
d[1,0]:=n;
while (d[1,0]+d[2,0]<>1) do
begin
if d[1,0]=0 then begin
for i:=t2+1 to d[2,0]+t2 do
begin
d[1,i-t2]:=d[2,i];
d[2,i]:=0;
end;
d[1,0]:=d[2,0];
d[2,0]:=0;
t1:=0; t2:=0;
end;
q:=0;
w:=0;
while (q+w<2) and (q<d[1,0]) and (w<d[2,0]) do
if d[1,q+t1+1]<=d[2,w+t2+1] then inc(q) else inc(w);
if q=d[1,0] then if q+w<2 then w:=w+(2-q);
if w=d[2,0] then if q+w<2 then q:=q+(2-w);
d[1,0]:=d[1,0]-q;
h:=0;
for i:=t1+1 to t1+q do
begin
h:=h+d[1,i];
d[1,i]:=0;
end;
for i:=t2+1 to t2+w do
begin
h:=h+d[2,i];
d[2,i]:=0;
end;
ans:=ans+h;
d[2,d[2,0]+t2+1]:=h;
d[2,0]:=d[2,0]+1-w;
t1:=t1+q;
t2:=t2+w;
end;
writeln(ans);
end.
小结：
用这样的方法来解哈夫曼问题，经过测试，时间同为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[0..110000] of int64;
ans1,ans2,h:int64;
d:array[1..2,0..110000] of z;
procedure gb(low,high:longint);
var
q,w,e,mid,k:longint;
begin
if low=high then exit;
mid:=(low+high) div 2;
gb(low,mid);
gb(mid+1,high);
q:=low;
w:=mid+1;
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:=1 to n do
read(a[i]);
p:=n;
while (p-1) mod (k-1)<>0 do
inc(p);
gb(1,p);
for i:=1 to p do
begin
d[1,i].w:=a[i];
if a[i]=0 then d[1,i].m:=-maxlongint;
end;
d[1,0].w:=p;
while d[1,0].w+d[2,0].w<>1 do
begin
if d[1,0].w=0 then begin
for i:=t2+1 to t2+d[2,0].w do
begin
d[1,i-t2].w:=d[2,i].w;
d[1,i-t2].m:=d[2,i].m;
d[2,i].w:=0; d[2,i].m:=0;
end;
d[1,0].w:=d[2,0].w;
d[2,0].w:=0;
t1:=0; t2:=0;
end; // zhuan yi
q:=0;
w:=0;
while (q+w<>k) and (q<d[1,0].w) and (w<d[2,0].w) do
if d[1,q+t1+1].w<=d[2,w+t2+1].w then inc(q) else inc(w);
if q+w<>k then if q=d[1,0].w then w:=w+(k-q-w) else q:=q+(k-w-q); // qu shu
d[1,0].w:=d[1,0].w-q;
m:=0;
d[2,d[2,0].w+t2+1].w:=ans1;
for i:=t1+1 to t1+q do
begin
ans1:=ans1+d[1,i].w;
d[1,i].w:=0;
if d[1,i].m>m then m:=d[1,i].m;
d[1,i].m:=0;
end;
for i:=t2+1 to t2+w do
begin
ans1:=ans1+d[2,i].w;
d[2,i].w:=0;
if d[2,i].m>m then m:=d[2,i].m;
d[2,i].m:=0;
end;
d[2,d[2,0].w+t2+1].w:=ans1-d[2,d[2,0].w+t2+1].w;
d[2,d[2,0].w+t2+1].m:=m+1;
d[2,0].w:=d[2,0].w-w+1;
t1:=t1+q;
t2:=t2+w;
end;
writeln(ans1);
writeln(m+1);
close(input);
close(output);
end.
总结
根据以上的分析，这种算法大大提高了运算速度，在数据比较大时，远远超过了堆。所以，这是一个优秀的解决哈夫曼树问题的算法。（算法为本人原创，严禁抄袭）