曹钦翔吧 关注:31贴子:76
  • 2回复贴,共1

左偏树!完美!!

只看楼主收藏回复

0


IP属地:美国1楼2008-03-27 15:29回复
    左偏树时间复杂度低,功能强大,编程复杂度也低。以后再也不用二叉堆了。附上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;


    IP属地:美国2楼2008-03-27 15:31
    回复
      左偏树在不需要删除非根节点的时候,是比较简洁的,否则还要多一段代码。所以左偏树不适合heap-dijkstra


      IP属地:美国3楼2008-04-04 11:06
      回复