二项式堆:证明合并在O(log n)时间内运行

Question

我正在阅读冈崎的纯功能数据结构,并尝试做一些练习.其中之一是证明二项式堆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节点，并且每个等级最多可以出现一次。因此，和中存在O(log n1)这样的树，其中和是 中的节点数堆和。）ts1O(log n2)ts2n1n2n=n1+n2

需要注意的关键点是，insTree每个等级最多调用一次（通过merge或递归），并且最大可能的等级是log_2(n)。原因如下：

如果insTree是叫自的话merge，那么r = rank t1 = rank t2，link(t1,t2)就会有等级r+1。所以我们可以说insTree是要求rank r+1。现在想想会发生什么merge(ts1', ts2')。设ts1' 和 中作为树出现的最小等级为。然后将再次从for row调用，因为两棵 Rank 树将链接起来形成一棵 Rank 树。但是，合并的堆因此不能包含 Rank 树，因此之前对 的调用不能比 进一步递归。ts2'r' >= r+1insTreemerger'+1r'r'+1merge(ts1', ts2')r'insTreer'

所以把事情放在一起：

• insTree被调用O(log n)次数最多，每次调用都是恒定时间（因为我们将递归计算为单独的调用）

• merge被调用的O(log n)次数最多，每次调用都是恒定时间（因为我们单独计算调用insTree并且link是恒定时间）

=> 整个合并操作是O(log n)。

编辑：顺便说一下，合并二项式堆非常类似于添加二进制数。当且仅当二进制数在该位置具有“1”时，大小的堆n才会具有排名树。合并此类堆时，您可以从最低级别到最高级别，或者从最不重要的位置到最重要的位置。相同等级的树需要链接（添加“一”），并插入/“携带”到较高等级的位置。rn2^r