Bottom Up Heap в ошибках Java - PullRequest
Новая
       26

Bottom Up Heap в ошибках Java

1 голос
/ 15 февраля 2011

Итак, я пытаюсь реализовать алгоритм 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, и я продолжаю получать некоторые ошибки, неизвестные мне.Мне было интересно, поможет ли кто-нибудь мне разобраться с некоторыми шагами алгоритма.

Я создал узел Heap с данными и указателями на левую и правую ссылки (или как их называет java).Входная последовательность представляет собой массив, который преобразуется в ArrayList.Вот что я передаю в функцию выше.

Я удаляю первый ключ из S и создаю новый узел с этим ключом.В моем примере я просто использую Integer s, а ключ установлен на ссылку на данные.

Затем я использую S1 = S.sublist(0, S.length/2) и S2 = S.sublist(S.length/2, S.length)

Вот что у меня такfar:

Передается ArrayList как 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 (), он выдает ошибку.

Спасибо!

Ответы [ 2 ]

0 голосов
/ 16 февраля 2011

Вы не можете remove, просматривая список.

Сделайте это: 

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;
    }
0 голосов
/ 15 февраля 2011

Я уже сталкивался с этим раньше, вывод таков: 

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

Это немного неясно из javadoc , однако sublist возвращает только вид исходного списка для данного диапазона. Взгляните на исходный код , чтобы увидеть, как происходит волшебство.

Если вы все еще хотите сохранить это, на мой взгляд, совершенно неуклюжую абстракцию, я бы порекомендовал вам использовать s.size() == 0 вместо s.isEmpty(). О, в соглашении также есть переменные, объявленные в camelcase .

...