java - Java 错误中的自下而上堆

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 keysOutput: a heap H storing the keys in Sif S is empty then    return an empty heapremove the first key, k, from SSplit S into subsequences S1 and S2, each of size (n-1)/2H1¬ bottomUpHeap(S1)H2¬ bottomUpHeap(S2)Create binary tree H such with k at root, H1 at left subtree and H2 at right subtreePerform down-heap bubbling from root if necessaryreturn H

It's been a while since I programmed in java and I keep getting some errors unknown to me. I was wondering if someone would help me out by clearing up some of the algorithm steps.

I created a Heap node with data and left and right reference pointers (or whatever java calls them). The input sequence is an array which gets converted to ArrayList. Thats what I pass into the function above.

I remove the first key from S and create a new node with that key. In my example, I'm just using Integers and the key is set to the data reference.

I then use S1 = S.sublist(0, S.length/2)andS2 = S.sublist(S.length/2, S.length)

Heres what i have so far:

An ArrayList is passed as S. Tree is defined as Tree(data, left, right). Thanks.

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() 它会抛出一个错误。

谢谢!

Answer 1

我以前有过这种经历，结论是你必须使用:

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

从javadoc看有点不清楚，但是 sublist 仅返回给定范围的原始列表的 View 。看看 source code看到奇迹发生。

如果你仍然希望保留这个，在我看来完全尴尬，抽象我会建议你使用 s.size() == 0 而不是 s.isEmpty()。哦，惯例也有它变量声明在camelcase .