左偏树时间复杂度低,功能强大,编程复杂度也低。以后再也不用二叉堆了。附上merge代码:
function merge(x,y:longint):longint;
var t:longint;
begin
if x=0 then exit(y);
if y=0 then exit(x);
if a[x]<a[y] then begin t:=x; x:=y; y:=t; end;
r[x]:=merge(r[x],y);
if dis[r[x]]>dis[l[x]] then begin t:=r[x]; r[x]:=l[x]; l[x]:=t; end;
dis[x]:=dis[r[x]]+1;
merge:=x;
end;
function merge(x,y:longint):longint;
var t:longint;
begin
if x=0 then exit(y);
if y=0 then exit(x);
if a[x]<a[y] then begin t:=x; x:=y; y:=t; end;
r[x]:=merge(r[x],y);
if dis[r[x]]>dis[l[x]] then begin t:=r[x]; r[x]:=l[x]; l[x]:=t; end;
dis[x]:=dis[r[x]]+1;
merge:=x;
end;