自下而上堆在Java中的錯誤

因此，即時通訊試圖在這裏實現bottomupheap算法： http://www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html 自下而上堆在Java中的錯誤

 
Algorithm bottomUpHeap(S) 
Input: a sequence S storing 2h-1 keys 
Output: a heap H storing the keys in S 
if S is empty then 
    return an empty heap 
remove the first key, k, from S 
Split S into subsequences S1 and S2, each of size (n-1)/2 
H1¬ bottomUpHeap(S1) 
H2¬ bottomUpHeap(S2) 
Create binary tree H such with k at root, H1 at left subtree and H2 at right subtree 
Perform down-heap bubbling from root if necessary 
return H

這已經有一段時間，因爲我編程Java和我不斷收到一些錯誤不認得我。我想知道是否有人會通過清除一些算法步驟來幫助我。

我創建了一個包含數據和左右引用指針（或任何java調用它們）的Heap節點。輸入序列是一個數組，它被轉換爲ArrayList。那就是我通過上面的函數。

我從S中刪除第一個密鑰，並用該密鑰創建一個新節點。在我的示例中，我只使用了Integer s，並將鍵設置爲數據引用。

然後我用 S1 = S.sublist(0, S.length/2) 和 S2 = S.sublist(S.length/2, S.length)

繼承人是我到目前爲止有：爲S. Tree被定義爲Tree(data, left, right)

的ArrayList傳遞。謝謝。

private Tree Heapify(List<Integer> S){ 

    if (S.isEmpty()){ 
     Tree emptyHeap = new Tree(); 
     return emptyHeap; 
    } 

    int tmpk = S.get(0); 
    S.remove(0); 

    int halfArr = S.size()/2; 

    List<Integer> S1 = S.subList(0, halfArr); 
    List<Integer> S2 = S.subList(halfArr, S.size()); 

    Tree k = new Tree(tmpk, Heapify(S1), Heapify(S2)); 

    //Downheap. 
    return null; 
}

從它似乎是什麼，當一個空的列表被傳遞使用的子表由於某種原因，當它不認爲它的空列表。它看起來像什麼時候它試圖做一些空的如S.isEmpty（）時會引發錯誤。

謝謝！

來源

2011-02-15 Matt

我在此之前已經經歷，得出的結論是，你必須使用：

S1 = new ArrayList(S.sublist(0, S.length/2));

這是從javadoc有點不清楚，但是sublist只返回原來的列表中給定範圍的視圖。看看source code看魔術發生。

如果你仍然希望保留這個，在我看來完全尷尬，抽象我建議你使用s.size() == 0而不是s.isEmpty()。哦，約定也有變量在camelcase中聲明。

來源

2011-02-15 20:39:13

有趣的是，java.util.concurrent.CopyOnWriteArrayList中的實施是「公共布爾的isEmpty（）{ \t返回大小（）== 0;} 」 – CMR 2011-02-16 15:54:11

遍歷列表時，您不能remove。

這樣做：

 
private Tree heapify(List list){ 

     if (list.isEmpty()){ 
      return null; 
     } 

     int tmpk = list.get(0); 
//  list.remove(0); 
     List s1 = null; 
     List s2 = null; 
     list = list.subList(1, list.size()); // change the list instead 

     int halfArr = list.size()/2; 

     s1 = list.subList(0, halfArr); 
     s2 = list.subList(halfArr, list.size()); 

     Tree k = new Tree(tmpk, heapify(s1), heapify(s2)); 

     return k; 
    }

來源

2011-02-15 21:00:08 CMR

其實，用[的ListIterator ]（http://download.oracle.com/javase/1.4.2/docs/api/java/util/ListIterator.html）除了你在哪裏看到迭代，你可以在迭代時刪除它嗎？ `list.remove（0）`沒有錯，也不會導致這裏的問題。 – 2011-02-15 21:02:30

自下而上堆在Java中的錯誤

回答

相關問題