优先级树是二叉树，其中只要 v 是 u 的 child，priority(u) ≥ priority(v)

Question

优先级树是二叉树，其中，只要 v 是 u 的 child，priority(u) ≥ priority(v)。那也就是说，它是一个堆，不一定是一棵完整的树。

(a) 设 H1 和 H2 是表示为树的两个堆。描述产生优先级的有效方法包含 H1 和 H2 的所有元素的树。该操作需要时间 O(log(|H1| + |H2|))，其中 |H| 表示堆 H 中的元素数。

我尝试了几种不同的方法，但无法获得正确的时间复杂度。谁能指出我正确的方向？

谢谢

Answer 1

免责声明：您对 "priority tree" 的定义很简单 min-heap。所以基本上你的问题只是将两个堆合并为一个。

一个简单的方法如下：获取具有较小根的堆并将另一个堆合并到其中。从要插入的堆的根开始，沿着任意路径，直到节点的值大于要插入的堆的根。用要插入的堆替换该节点。现在您有一个要插入的新堆（您刚刚从堆中删除的堆）。从刚刚插入的节点开始继续上述操作，直到要插入的堆最终为空。

//if at least one heap is empty, the job is already done
if H1.isEmpty()
    return H2
if H2.isEmpty()
    return H1

//select heap to insert into and heap to be inserted
node insInto, toIns, prntInsInto
if H1.getRoot() > H2.getRoot()
    insInto = H2.getRoot()
    toIns = H1.getRout()
else
    insInto = H1.getRoot()
    toIns = H2.getRoot()

heap result = insInto
//merge
while toIns != null
    if insInto == null
       //we've run to the lower end of the heap to insert into
       //just append the heap to insert and youre done
       prntInsInto.setLeftChild(toIns)
       return result

    if insInto > toIns
       //replace node in heap into which is insert with the root of the heap to insert
       prntInsInto.replace(insInto , toIns)

       //removed subtree becomes new heap to insert
       //and inserted subtree becomes new heap into which is inserted
       node tmp = toIns
       toIns = insInto
       insInto = tmp

   //I selected the left child for the search, this is
   //completely random, you could even replace it with the
   //larger of the two children for better efficiency 
   prntInsInto = insInto
   insInto = insInto.leftChild()

return result

这个算法利用了这样一个事实，即 min-heaps 可以递归定义为 H = (N , L , R)，其中 N 是堆的根，L 和 R分别是左右children，也是堆

此算法以 worst-cast O(log |H1| + log |H2|) 运行。更快是不可能的。

编辑：
刚刚注意到评论说堆存储为数组。在这种情况下，对数运行时间根本不可能，因为必须遍历所有元素才能实现该运行时间。因此，在这种情况下，O(|H1| + |H2|) 将是您能做的最好的，因为上述算法依赖于这样一个事实，即可以在 O(1) 中操作已经存在的 data-structure，而数组则没有.

优先级树是二叉树，其中只要 v 是 u 的 child，priority(u) ≥ priority(v)

A priority tree is a binary tree where, whenever v is a child of u, priority(u) ≥ priority(v)

algorithm

math

heap

priority-queue

time-complexity