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

Question

我正在通读 Okasaki's Purely Functional Data Structures 并尝试做一些练习。其中之一是证明二项式堆 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 个节点，每个等级最多可以出现一次。因此，在ts1中有O(log n1)个这样的树，在ts2中有O(log n2)个，其中n1和n2是节点的个数堆和 n=n1+n2.)

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

如果从 merge 调用 insTree，则说 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 的树。合并此类堆时，您会从最低等级到最高等级——或者从最不重要到最重要的位置。相同等级的树需要链接（'ones'添加），并插入/"carried"到更高等级的位置。

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

Binomial Heaps: proof that merge runs in O(log n) time

algorithm

big-o

functional-programming

ml

data-structures