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）时间

回答

相关问题