1

所以，我试图在这里实现bottomupheap算法：http: //www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html

算法bottomUpHeap(S)
输入：存储 2h-1 个键的序列 S
输出：一个堆 H 将密钥存储在 S 中
如果 S 为空，则
    返回一个空堆
从 S 中删除第一个密钥 k
将 S 拆分为子序列 S1 和 S2，每个子序列的大小为 (n-1)/2
H1¬bottomUpHeap(S1)
H2¬bottomUpHeap(S2)
创建二叉树H，其中k在根，H1在左子树，H2在右子树
如有必要，从根执行向下堆冒泡
返回 H

自从我用 java 编程以来已经有一段时间了，而且我不断收到一些我不知道的错误。我想知道是否有人会通过清理一些算法步骤来帮助我。

我创建了一个带有数据和左右引用指针（或 java 调用它们的任何东西）的堆节点。输入序列是一个数组，它被转换为ArrayList. 这就是我传递给上面函数的内容。

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

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

继承人我到目前为止：

AnArrayList作为 S 传递。Tree定义为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() 之类的空对象执行任何操作时会引发错误。

谢谢！

4

2 回答 2

0

我以前经历过，结论是你必须使用：

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

从javadoc有点不清楚，但是sublist只返回给定范围的原始列表的视图。看看源代码，看看奇迹发生了。

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

于 2011-02-15T20:39:13.347 回答
0

remove遍历列表时不能。

做这个：

私有树堆（列表列表）{

        if (list.isEmpty()){
            返回空值；
        }

        int tmpk = list.get(0);
// list.remove(0);
        列表 s1 = null;
        列表 s2 = null;
        list = list.subList(1, list.size()); // 改为更改列表

        int halfArr = list.size()/2;

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

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

        返回 k；
    }
于 2011-02-15T21:00:08.813 回答