Куча снизу вверх в Java - PullRequest
Новая
       24

Куча снизу вверх в Java

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

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

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

Я тогда использую S1 = S.sublist(0, S.length/2) а также S2 = S.sublist(S.length/2, S.length)

Теперь я бы предположил, что H1 и H2 - это кучи или узлы? Здесь я немного запутался в том, что мне следует делать в Java.

Тогда для следующей части, похоже, я должен сделать k.left = H1 и k.right = H2

Я не совсем уверен, когда он говорит "k в корне". Разве k не является корневым узлом? Если бы это было так, я бы тоже сделал пузырек с k? Тогда в самом конце H будет k и в этот момент?

Извините, что у меня нет кода для публикации, но ошибки, которые я получаю, находятся в подсписке рекурсивного вызова.

Обновлен:

Значение 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;
}

Спасибо!

1 Ответ

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

Теперь я бы предположил, что H1 и H2 - это кучи или узлы?

На первой странице ваших заметок говорится:

"Куча - это двоичное дерево H, которое хранит набор ключей на своих внутренних узлах ..."

Здесь я немного запутался в том, что мне делать в Java.

Существует несколько способов сделать это, но очевидным представлением является класс Tree, имеющий значение и ссылки на левое и правое поддеревья.

Я не совсем уверен, когда он говорит k в корне. Разве k не является корневым узлом?

Это корень кучи, созданной текущим вызовом bottomUpHeap. Обратите внимание, что алгоритм является рекурсивным!

Если бы это было так, я бы тоже сделал пузырек из k? Тогда в самом конце H также будет k в этой точке?

Вот что он говорит.

У меня нет кода для публикации, но ошибки, которые я получаю, находятся в подсписке рекурсивного вызова.

Мы не можем помочь, если вы не отправите код и ошибки.

...