二項ヒープ：O（log n）時間でマージが実行されるという証明

Question

私はOkasaki's Purely Functional Data Structuresを読んでおり、いくつかの演習をしようとしています。それらのうちの1つは、二項ヒープmergeがO(log n)時間かかることを証明することです。ここで、nはヒープ内のノードの数です。

functor BinomialHeap (Element:ORDERED):HEAP= 
struct 
    structure Elem=Element 
    datatype Tree = Node of int*Elem.T*Tree list 
    type Heap = Tree list 
    fun link (t1 as Node (r,x1,c1), t2 as Node (_,x2,c2))= 
    if Elem.leq(x1,x2) 
    then Node (r+1,x1,t2::c1) 
    else Node (r+1,x2,t1::c2) 
    fun insTree (t,[])=[t] 
    |insTree (t,ts as t'::ts')= 
     if rank t < rank t' then t::ts else insTree(link(t,t'),ts') 
    fun insert (x,ts)=insTree(Node(0,x,[]),ts) (*just for reference*) 
    fun merge (ts1,[])=ts1 
    |merge ([],ts2)=ts2 
    |merge (ts1 as t1::ts1', ts2 as t2:ts2')= 
     if rank t1 < rank t2 then t1::merge(ts1',ts2) 
     else if rank t2 < rank t1 then t2::merge(ts1,ts2') 
     else insTree (link(t1,t2), merge (ts1',ts2')) 
end 

mergeがmax(numNodes ts1, numNodes ts2)回自分自身を呼び出すことは明らかであるが、insTreeはO(log n)最悪のケースであるため、あなたはmergeがO(log n)でどのように説明できますか？

Answer 1

最初に、mergeが最大で(numNodes ts1 + numNodes ts2)回呼び出され、これはO(log n)回であることに注意してください。 （ただ、明確にするために、ts1とts2がランクrのようにツリーが正確に2^rのノードが含まれており、各ランクは、最高1回発生する可能性があります場合は、二項木のリストである。したがって、O(log n1)な木は、ts2でts1とO(log n2)でありますn1とn2はヒープとn=n1+n2内のノードの数である場合。）

注意すべき重要な点は、insTree）がmergeを介して、または再帰的のいずれか（各ランクのために最大で一度呼ばれ、可能な最大ランクであることですlog_2(n)。理由は以下の通りである：insTreeがmergeから呼び出され

場合は、r = rank t1 = rank t2を言う、とlink(t1,t2)はランクr+1を持つことになります。したがって、にinsTreeが呼び出されたとします。今度はmerge(ts1', ts2')で何が起こるか考えてみましょう。木として生じる最小ランクをts1'と とすると、r' >= r+1となります。次にinsTreeは、mergeからランクr'+1を再度呼びます。これは、ランクr'の2つのツリーがリンクして、ランクr'+1のツリーを形成するためです。ただし、merge(ts1', ts2')のマージされたヒープのツリーは、ランクr'のツリーを含んでいる可能性があり、前のinsTreeの呼び出しはr'より後で再帰できません。

だから、物事をまとめる：各呼び出しの時定数であること（私たちは別のコールと再帰を数えるため）

mergeがで呼ばれて

• insTreeは、最もO(log n)回で呼ばれています多くの場合、O(log n)回、各コールは一定時間です（insTreeへのコールを個別にカウントし、linkは一定時間です）

=>マージ操作全体がO(log n)です。

編集：ちなみに、バイナリヒープをマージするのは、バイナリ数を追加するのと非常によく似ています。サイズがnのヒープは、2進数nが2^rの位置に '1'を持つ場合に限り、ランクrのツリーを持ちます。このようなヒープをマージするときは、最下位ランクから最上位ランクまで、または最下位から最上位まで進んでください。同じランクの木は、リンクされていなければならず（ '1'が追加されている）、上位ランクの位置に挿入/運ばれている必要があります。