Purely Functional Data Structures (page 22)での Okasaki の実装は、2 つの部分でそれを行います。1 つはフォレストをマージし、もう 1 つはキャリーを伝播します。これは、ワンパスバージョンよりも分析が難しく、おそらく遅いと思います。何か不足していますか？
岡崎の実装：
ファンクター BinomialHeap (要素:ORDERED):HEAP=
構造体
構造 Elem=要素
datatype Tree = int*Elem.T*Tree リストのノード
タイプ ヒープ = ツリー リスト
fun link (ノード (r,x1,c1) としての t1、ノード (_,x2,c2) としての t2)=
if Elem.leq(x1,x2)
ノード (r+1,x1,t2::c1)
else ノード (r+1,x2,t1::c2)
fun 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
|マージ (t1::ts1' としての ts1、t2:ts2' としての ts2)=
ランク t1 < ランク t2 の場合 t1::merge(ts1',ts2)
そうでなければランク t2 < ランク t1 なら t2::merge(ts1,ts2')
else insTree (link(t1,t2), merge (ts1',ts2'))
終わり
すべてのキャリーを伝搬するコストの上限を証明する必要があるため、これを分析するのは難しいと思います (以下を参照)。私が思いついたトップダウン マージの実装は、明らかに O(log n) です。ここで、n はより大きなヒープのサイズです。
ファンクター BinomialHeap (要素:ORDERED):HEAP=
構造体
構造 Elem=要素
datatype Tree = int*Elem.T*Tree リストのノード
タイプ ヒープ = ツリー リスト
楽しいランク (Node(r,_,_))=r
fun link (ノード (r,x1,c1) としての t1、ノード (_,x2,c2) としての t2)=
if Elem.leq(x1,x2)
ノード (r+1,x1,t2::c1)
else ノード (r+1,x2,t1::c2)
fun 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)
fun merge(ts1,[])=ts1
|merge([],ts2)=ts2
|マージ (t1::ts1' としての ts1、t2::ts2' としての ts2)=
ランク t1 < ランク t2 の場合 t1::merge(ts1',ts2)
そうでなければランク t2 < ランク t1 なら t2::merge(ts1,ts2')
else mwc(リンク(t1,t2),ts1',ts2')
(*mwc=キャリーとマージ*)
および mwc (c,ts1,[])=insTree(c,ts1)
|mwc (c,[],ts2)=insTree(c,ts2)
|mwc (c,ts1 as t1::ts1', ts2 as t2::ts2')=
ランク c < ランク t1 の場合
ランク c < ランク t2 の場合、 c::merge(ts1,ts2)
else mwc(リンク(c,t2),ts1,ts2')
else mwc(リンク(c,t1),ts1',ts2)
終わり
Okasaki の実装が O(log n) であることの証明: キャリーが「高価」(1 つまたは複数のリンクが必要) である場合、ゼロが生成されます。したがって、次の高価なキャリーは、そのポイントに到達すると停止します。そのため、すべてのキャリーを伝播するために必要なリンクの総数は、伝播前のバイナリ表現の全長程度以下であり、これは ceil(log n) によって上に制限されます。ここで、n はより大きなヒープのサイズです。