바닥까지 힙 자바 오류

Question

는

그래서, 여기에 bottomupheap 알고리즘을 구현하기 위해 노력하고 메신저 : 그것은 잠시이었다 http://www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html

 
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 

이후 나는 자바 프로그래밍 나는 나에게 알 수없는 약간의 오차가 점점 계속. 누군가가 알고리즘 단계 중 일부를 정리하여 나를 도울 수 있는지 궁금 해서요.

데이터와 왼쪽 및 오른쪽 참조 포인터 (또는 자바를 호출하는 포인터)가있는 힙 노드를 만들었습니다. 입력 순서는 ArrayList으로 변환되는 배열입니다. 내가 위의 함수에 전달하는 것입니다.

S에서 첫 번째 키를 제거하고 해당 키를 사용하여 새 노드를 만듭니다. 필자의 예에서는 Integer을 사용하고 있으며 키는 데이터 참조로 설정되어 있습니다.

나는 다음 S1 = S.sublist(0, S.length/2) 및 S2 = S.sublist(S.length/2, S.length)

를 사용 Heres는 내가 지금까지 무엇을 : 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()와 같이 비어있는 곳에서 아무 것도하지 않으면 오류가 발생합니다.

감사합니다. 지정된 범위의 원래 목록 그러나 sublist 수익률 만보기

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

그것은 javadoc에서 약간 불분명 :

Answer 1

나는이 전에 경험을했습니다, 결론은 사용해야한다는 것입니다. 마법이 일어나는 것을 보시려면 source code을보십시오.

여전히 이것을 유지하고 싶다면, 제 생각에 완전히 어색하고 추상적인데 s.isEmpty() 대신 s.size() == 0을 사용하는 것이 좋습니다. 아, 대회도 변수는 camelcase에 선언되어 있습니다.

Answer 2

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; 
    }