0

所以,我试图在这里实现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)

现在我假设 H1 和 H2 是堆还是节点?这是我对我应该在java中做什么感到有点困惑的地方。

然后对于下一部分看起来我应该k.left = H1k.right = H2

我不确定它什么时候说“k at root”。不是k根节点吗?如果是这样的话,我也会做一个向下的泡沫k吗?那么最后也会Hk这一点上吗?

抱歉,我没有要发布的代码,但我得到的错误位于递归调用的子列表中。


更新:

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

谢谢!

4

1 回答 1

0

现在我假设 H1 和 H2 是堆还是节点?

你讲义的第一页是这样写的:

“堆是一棵二叉树 H,它在其内部节点存储一组键......”

这是我对我应该在java中做什么感到有点困惑的地方。

有不止一种方法可以做到这一点,但显而易见的表示是具有值的 Tree 类,以及左右子树的引用。

我不确定它什么时候在根上说 k 。k不是根节点吗?

它是当前调用创建的堆的根bottomUpHeap。请注意,该算法是递归的!

如果是这样的话,我也会从 k 做一个下堆泡沫吗?那么在这一点上,最后 H 也会是 k 吗?

这就是它所说的。

我没有要发布的代码,但我得到的错误位于递归调用的子列表中。

除非您发布代码和错误,否则我们无能为力。

于 2011-02-12T16:00:44.980 回答