優先級樹是一棵二叉樹，其中每當v是u的子元素時，優先級（u）≥優先級（v）

Question

優先級樹是一棵二叉樹，其中每當v是u的孩子時，優先級樹就是priority(u) ≥ priority(v)。那 是，它是不一定是一棵完整的樹的堆。 （a）讓H1和H2表示爲樹的兩個堆。描述一種有效的方法來生成包含H1和H2所有元素的優先級樹 。該操作需要花費時間O(log(|H1| + |H2|))，其中|H|表示堆中元素的數量H.

我試過幾種不同的方法，但無法獲得正確的時間複雜度。任何人都可以將我指向正確的方向嗎？

謝謝

Answer 1

免責聲明：您的「優先權樹」的定義是一個簡單的最小堆。所以基本上你的問題只是將兩堆合併爲一個。

一個簡單的方法如下：把堆放在較小的根上並將其他堆合併到堆中。從插入的堆的根部開始，並遵循任意路徑，直到該節點的值大於要插入的堆的根部。將該節點替換爲要插入的堆。現在你已經有了一個新的堆（你剛剛從堆中移除的堆）。只需從剛剛插入的節點開始，直到要插入的堆最終爲空。

//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)來定義，其中N是堆的根和L和R分別是左和右孩子，這是堆以及。

此算法與最差鑄造O(log |H1| + log |H2|)一起運行。更快是不可能的。

編輯：
只是注意到這個評論說，堆被存儲爲數組。在這種情況下，對數運行時是不可能的，因爲必須遍歷所有元素才能實現該運行時。因此O(|H1| + |H2|)將是你可以在這種情況下做的最好的，因爲上面的算法依賴於事實上已經存在的數據結構可以在O(1)中操作，而數組結構沒有給出。