Bottom Up Heap in Java errors

So, im trying to implement the bottomupheap algorithm here: 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

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) and S2 = S.sublist(S.length/2, S.length)

H开发者_运维百科eres 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;
}

From what it seems is that when an empty list is passed it doesn't think its an empty list when using sublist for some reason. It looks like when it tries to do anything on an empty such as S.isEmpty() it throws an error.

Thanks!

I've experience this before, the conclusion is that you have to use:

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

It's a little unclear from the javadoc, however sublist returns only a view of the original list for the given range. Have a look at the source code to see the magic happen.

If you still wish to retain this, in my opinion completely awkward, abstraction I would recommend you to use s.size() == 0 instead of s.isEmpty(). Oh, convention also has it variables are declared in camelcase.

You cannot remove while iterating through the list.

Do this:

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