優先度ツリーは、vがuの子であるときはいつでも優先度（u）≥優先度（v）であるバイナリツリーです。

Question

優先度ツリーは、vがuの子であるときは常にpriority(u) ≥ priority(v)です。その は、必ずしも完全なツリーではないヒープです。

（a）H1とH2をツリーとして表される2つのヒープとする。 H1とH2のすべての要素を含む優先度の高い木を生成する効率的な方法を記述してください。 操作にはO(log(|H1| + |H2|))の時間がかかります。|H|はヒープHの要素数を意味します。

私はいくつかの方法を試しましたが、適切な時間の複雑さを得ることはできません。誰かが私を正しい方向に向けることができますか？

おかげ

Answer 1

免責事項：「優先ツリー」のあなたの定義は、単純な分、ヒープです。ですから、基本的には、2つのヒープを1つにマージするだけです。

単純なアプローチは次のとおりです。小さなルートでヒープを取り出し、もう一方のヒープをその中にマージします。挿入されるヒープのルートから開始し、ノードが挿入するヒープのルートよりも大きな値を持つまで、任意のパスに従います。そのノードを挿入するヒープに置き換えます。今度は新しいヒープ（ヒープから削除したヒープ）を挿入します。挿入するヒープが最後に空になるまで、ちょうど挿入したノードから上記の作業を進めてください。 Nヒープの根及びLでありRそれぞれヒープがaswellであり、左右の子供である場合

//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 

このアルゴリズムは、その分、ヒープをH = (N , L , R)のように再帰的に定義することができる、という事実を利用します。

これは最悪のキャストO(log |H1| + log |H2|)で実行されます。もっと早くすることはできません。

編集：
ヒープが配列として格納されているとのコメントに気付きました。この場合、ランタイムを達成するためにはすべての要素をトラバースする必要があるため、対数ランタイムは単純に不可能です。したがって、ですでに存在するデータ構造を操作できるという事実に依存しているため、O(|H1| + |H2|)はその場合に可能な限り最善の方法です。