二項式堆插入java

我無法插入二項堆，當我調用插入1它打印（1），然後我插入2它顯示（2），而不是（1（2）），然後三個它顯示（3）而不是（3）（1（2））。如果有人能幫我弄清楚我的問題，我將非常感激。先謝謝你。這裏是我的代碼二項式堆插入java

public class BHeap { 

    int key; 
    int degree;//The degree(Number of children) 
    BHeap parent, leftmostChild, rightmostChild, rightSibling,root,previous,next; 
    public BHeap(){ 
     key =0; 
     degree=0; 
     parent =null; 
     leftmostChild=null; 
     rightmostChild=null; 
     rightSibling=null; 
     root=null; 
     previous=null; 
     next=null; 
    } 
    public BHeap merge(BHeap y){ 
     BHeap newHeap = new BHeap(); 
     BHeap currentHeap = y; 
     BHeap nextHeap = y.rightSibling; 
     while(currentHeap.rightSibling !=null){ 
      if(currentHeap.degree==nextHeap.degree){ 
       if(currentHeap.key<nextHeap.key){ 
        if(currentHeap.degree ==0){ 
         currentHeap.leftmostChild=nextHeap; 
         currentHeap.rightmostChild=nextHeap; 
         currentHeap.rightSibling=nextHeap.rightSibling; 
         nextHeap.rightSibling=null; 
         nextHeap.parent=currentHeap; 
         currentHeap.degree++; 
        } 
        else{ 
         newHeap = currentHeap; 
         newHeap.rightmostChild.rightSibling=nextHeap; 
         newHeap.rightmostChild=nextHeap; 
         nextHeap.parent=newHeap; 
         newHeap.degree++; 
         nextHeap.rightSibling=null; 
         nextHeap=newHeap.rightSibling; 
        } 
       } 
       else{ 
        if(currentHeap.degree==0){ 
         nextHeap.rightmostChild=currentHeap; 
         nextHeap.rightmostChild.root = nextHeap.rightmostChild;//add 
         nextHeap.leftmostChild=currentHeap; 
         nextHeap.leftmostChild.root = nextHeap.leftmostChild;//add 
         currentHeap.parent=nextHeap; 
         currentHeap.rightSibling=null; 
         currentHeap.root=currentHeap;//add 
         nextHeap.degree++; 
        } 
        else{ 
         newHeap=nextHeap; 
         newHeap.rightmostChild.rightSibling=currentHeap; 
         newHeap.rightmostChild=currentHeap; 
         currentHeap.parent= newHeap; 
         newHeap.degree++; 
         currentHeap=newHeap.rightSibling; 
         currentHeap.rightSibling=null; 
        } 
       } 
      } 
      else{ 
       currentHeap=currentHeap.rightSibling; 
       nextHeap=nextHeap.rightSibling; 
      } 
     } 
     return y; 
    } 
    public void Insert(int x){ 
     BHeap newHeap= new BHeap(); 
     newHeap.key=x; 
     if(this.root==null){ 
      this.root=newHeap; 
     } 
     else{ 
      this.root = merge(newHeap); 
     } 
    } 
    public void Display(){ 
     System.out.print("("); 
     System.out.print(this.root.key); 
     if(this.leftmostChild != null){ 
      this.leftmostChild.Display(); 
     } 
     System.out.print(")"); 
     if(this.rightSibling!=null){ 
      this.rightSibling.Display(); 
     } 
    } 
}

來源

2013-10-29 King11

你有沒有嘗試過調試它？ – Cruncher

@Cruncher是的，我做了調試，所有東西都指向它指向的位置並正確設置所有東西 – King11

@Rod沒有代碼，您的問題就沒有永久的價值。如果您不想顯示它，請刪除整個問題。 – EJP

當你插入，你是一個新的BHeap對象，然後傳遞，爲merge()。你的新BHeap沒有rightSibling，所以你跳過整個while循環，只是返回新的BHeap。所以新的BHeap成爲整個BHeap的root，你扔掉了之前的東西。

更新：我不打算編寫僞代碼，因爲它就在您的代碼中。

所以你做一個新的BHeap和Insert(1)。您的Insert方法會產生第二個新的BHeap，然後檢查當前的BHeap的root。這是空的，所以第二個BHeap成爲root。沒關係。

現在你Insert(2)。再次創建另一個BHeap。這一次BHeap的root不爲空，所以我們呼叫merge通過新的BHeap。請注意，現在將此新BHeap（merge內）稱爲y。另外請注意，除了設置key字段外，您還沒有對此新的BHeap做任何處理，因此的所有其他字段均爲空。

Inside merge您又製造了另一個BHeap對象，並且製作了另一個參考currentHeap，它指的是y。（同樣，只有key字段已被設置，因此所有其他字段都爲空。）您將y的rightSibling指爲nextHeap，然後是while循環。 while循環表示雖然rightSibling的currentHeap不爲空，但要做一堆東西。

但正如我上面所說的，一切約currentHeap（又名y又名你Insert創建全新的BHeap）是空。因此整個while循環被跳過，並且您從merge返回y。

Insert然後接受來自y的返回值並將其設置爲當前BHeap的root。舊垃圾root被丟棄，坐在角落裏，悲傷的命運中哭泣，然後垃圾收集器出現並將其洗入早期墳墓。新的root高聲歡呼和統治至尊，BHeap（和BHeap的唯一成員）的國王...直到你撥打Insert(3)。

你呢？您將學習如何使用調試器。

來源

2013-10-29 18:39:14 dcsohl

你可能會寫你的答案Psuedo代碼，以幫助我瞭解你說的更清楚嗎？ – King11

已更新的答案。 – dcsohl

在你的方法merge你通過一個BHeap對象y。你確實改變了你創建的BHeap對象，並在insert方法中傳遞給merge不會添加任何兄弟。 while循環從不運行。

此外，我認爲你可能想要檢查你的merge方法。看起來你並沒有考慮到你正在合併的當前BHeap，並簡單地重新格式化了給定的BHeap參數。

來源

2013-10-29 18:45:49

二項式堆插入java

回答

相關問題