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 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 调用它们）的堆节点。输入序列是一个被转换为 ArrayList 的数组。这就是我传递给上面函数的内容。

我从 S 中删除第一个键并使用该键创建一个新节点。在我的示例中，我仅使用 Integer 并将键设置为数据引用。

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

这是我到目前为止所拥有的：

ArrayList 作为 S.Tree 传递code> 定义为Tree(data, left, right)。谢谢。

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 仅返回给定范围的原始列表的视图。查看源代码来了解它的魔力发生。

如果您仍然希望保留这一点，在我看来完全尴尬的抽象，我建议您使用 s.size() == 0 代替 s.isEmpty() 。哦，约定也有变量在 camelcase 中声明。

Answer 2

迭代列表时无法删除。

这样做：

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