算法介绍：
哈夫曼树的思路及实现众所周知，大部分是用堆来维护和实现，这种思路比较清晰，在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代码
总结
根据以上的分析，这种算法大大提高了运算速度，在数据比较大时，远远超过了堆。所以，这是一个优秀的解决哈夫曼树问题的算法。（算法为本人原创，严禁抄袭）