4

Okasaki 在Purely Functional Data Structures（第 22 页）中的实现分为两部分：一是合并森林，一是传播进位。这让我觉得比一次性版本更难分析，也可能更慢。我错过了什么吗？

冈崎的实现：

函子 BinomialHeap (元素:ORDERED):HEAP=
结构
  结构元素=元素
  数据类型 Tree = int*Elem.T*Tree 列表的节点
  类型堆 = 树列表
  有趣的链接（t1 作为节点（r，x1，c1），t2 作为节点（_，x2，c2））=
    如果 Elem.leq(x1,x2)
    然后节点 (r+1,x1,t2::c1)
    否则节点 (r+1,x2,t1::c2)
  有趣的 insTree (t,[])=[t]
     |insTree (t,ts as t'::ts')=
        如果排名 t < 排名 t' 则 t::ts 否则 insTree(link(t,t'),ts')
  fun insert (x,ts)=insTree(Node(0,x,​​[]),ts) (*仅供参考*)
  有趣的合并 (ts1,[])=ts1
     |合并 ([],ts2)=ts2
     |合并（ts1 作为 t1::ts1'，ts2 作为 t2:ts2'）=
        如果排名 t1 < 排名 t2 则 t1::merge(ts1',ts2)
        否则，如果排名 t2 < 排名 t1 则 t2::merge(ts1,ts2')
        否则 insTree（链接（t1，t2），合并（ts1'，ts2'））
结尾

这让我觉得很难分析，因为你必须证明传播所有进位的成本的上限（见下文）。我想出的自上而下的合并实现更明显是 O(log n) 其中 n 是较大堆的大小：

函子 BinomialHeap (元素:ORDERED):HEAP=
结构
  结构元素=元素
  数据类型 Tree = int*Elem.T*Tree 列表的节点
  类型堆 = 树列表
  有趣的排名 (Node(r,_,_))=r
  有趣的链接（t1 作为节点（r，x1，c1），t2 作为节点（_，x2，c2））=
    如果 Elem.leq(x1,x2)
    然后节点 (r+1,x1,t2::c1)
    否则节点 (r+1,x2,t1::c2)
  有趣的 insTree (t,[])=[t]
     |insTree (t,ts as t'::ts')=
        如果排名 t < 排名 t' 则 t::ts 否则 insTree(link(t,t'),ts')
  有趣的插入 (x,ts)=insTree(Node(0,x,​​[]),ts)

  有趣的合并（ts1，[]）=ts1
     |合并([],ts2)=ts2
     |合并（ts1 作为 t1::ts1'，ts2 作为 t2::ts2'）=
        如果排名 t1 < 排名 t2 则 t1::merge(ts1',ts2)
        否则，如果排名 t2 < 排名 t1 则 t2::merge(ts1,ts2')
        否则 mwc（链接（t1，t2），ts1'，ts2'）
  (*mwc=与进位合并*)
  和 mwc (c,ts1,[])=insTree(c,ts1)
     |mwc (c,[],ts2)=insTree(c,ts2)
     |mwc (c,ts1 作为 t1::ts1', ts2 作为 t2::ts2')=
        如果等级 c < 等级 t1
        那么如果排名 c < 排名 t2 则 c::merge(ts1,ts2)
                  否则 mwc（链接（c，t2），ts1，ts2'）
        否则 mwc（链接（c，t1），ts1'，ts2）
结尾

证明 Okasaki 的实现是 O(log n)：如果进位是“昂贵的”（需要一个或多个链接），那么它会产生零。因此，下一个昂贵的进位将在到达该点时停止。因此，传播所有进位所需的链接总数不超过传播前二进制表示的总长度，该长度以 ceil(log n) 为界，其中 n 是较大堆的大小。

4

0 回答 0