Binomial堆：證明合併運行在O（日誌n）時間

我正在閱讀Okasaki's Purely Functional Data Structures並正在嘗試做一些練習。其中之一是證明二項式堆merge需要O(log n)時間，其中n是堆中的節點數。Binomial堆：證明合併運行在O（日誌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)？

來源

2015-09-05 Justin Raymond

首先注意merge最多會被調用(numNodes ts1 + numNodes ts2)次，這是O(log n)次。（只是要清楚，ts1和ts2是二叉樹，其中排名r這樣的樹只包含2^r節點列表，最多一次。因此，有在ts2ts1和O(log n2)O(log n1)這種樹可以出現各級別，其中n1和n2是在堆和n=n1+n2節點的數量。）

關鍵的一點要注意的是，insTree被稱爲最多一次每個等級（通過merge或遞歸），而最大的可能秩log_2(n)。其原因如下：

如果insTree從merge叫，然後說r = rank t1 = rank t2，並且link(t1,t2)排名爲r+1。所以我們假設insTree被稱爲等級r+1。現在想想merge(ts1', ts2')會發生什麼。讓出現在ts1'和ts2'中的最小排名爲r' >= r+1。然後insTree將從merge再次被調用，因爲排名爲r'+1，因爲排名r'的兩棵樹將被鏈接以形成排名爲r'+1的樹。但是，合併的堆merge(ts1', ts2')可以因此而不是包含排名r'的樹，因此以前調用insTree因此可能不會比r'進一步遞歸。

所以把東西放在一起：

insTree被稱爲最多O(log n)次，每次通話是固定的時間（因爲我們算遞歸作爲一個單獨的呼叫）
merge被稱爲在大多數爲O(log n)次，每次通話時間不變（因爲我們分別計數到insTree的呼叫和link是不變的時間）

=>整個合併操作是O(log n)。

編輯：順便說一句，合併二項堆非常像添加二進制數字。當且僅當二進制數n在2^r位置具有'1'時，堆n的堆將具有等級r的樹。合併這些堆時，您可以從最低級到最高級 - 對最重要的位置最不重要。需要連接相同級別的樹（添加'1'），並插入/「攜帶」到更高等級的位置。

來源

2015-09-06 00:23:16 m7thon

你可以擴展這個：「但是，合併堆'merge（ts1'，ts2'）'因此不能包含一個等級<='r''」的樹。我相信如果'ts1'有一棵等級爲「r」的樹並且'ts2'不包含'r''的樹。 –

忘記「<='r''」，如果應該只是'r'（只是固定的）。 'r''被選爲'ts1'' *和*'ts2''中樹的最小等級。這些樹被合併（形成一個等級'r'+ 1'樹），所以在合併堆merge（ts1'，ts2'）'中，不再有一個等級爲「r」的樹。之前對'insTree'的調用可以緩解一些等級（也就是說，只要'ts1'或'ts2'包含這樣一個等級的樹），但是這個遞歸必須停止在'r'級「'。另外，下一次從'merge'調用'insTree'出現在'r'+ 1'級。所以'insTree'每個級別最多被調用一次。 – m7thon

Binomial堆：證明合併運行在O（日誌n）時間

回答

相關問題