Java Arraylist Куча реализации

Question

Я пытаюсь реализовать метод insert() для реализации кучи на основе массивов, но всякий раз, когда я тестирую метод, вставляя более одного целого числа, где по крайней мере одно из них больше, чем ~ 4, программа занимает навсегда запустить. Например, заявка heap.insert(1) и heap.insert(8) вместе в основной функции будет выполняться навсегда. Вот моя куча класс:

import java.util.*; 


public class Heap<E extends Comparable<E>> implements HeapAPI<E> 
{ 
    /** 
    * A complete tree stored in an array list representing this 
    * binary heap 
    */ 
    private ArrayList<E> tree; 

    /** 
    * Constructs an empty heap 
    */ 
    public Heap() 
    { 
     tree = new ArrayList<E>(); 
    } 

    public boolean isEmpty() 
    { 
     return tree.isEmpty(); 
    } 

    public void insert(E obj) 
    { 
     tree.add(tree.size(), obj); 
     siftUp(tree.size() - 1); 
    } 

    /** 
    * siftUp from position k. The key or node value at position 
    * may be greater that that of its parent at k/2. 
    * @param k position in the heap arraylist 
    */ 
    private void siftUp(int k) 
    { 
     E v = tree.get(k); 
     while (v.compareTo(tree.get(k/2)) == 1) 
     { 
      tree.add(k, tree.get(k/2)); 
      k = k/2; 
     } 
     tree.add(k, v); 
    } 

    public int size() 
    { 
     return tree.size(); 
    } 
} 

Это псевдокод дал нам мой профессор, что я моделировал insert() и siftUp() методы из:

Программа работает для небольших чисел, например, если Я набираю heap.insert(1) кучу раз подряд, но никогда не заканчивает работу, если я меняю одно из чисел на большее целое число. Ошибок не возникает, так как они не заканчиваются, когда я пытаюсь запустить программу. Я не уверен, что происходит. Любая помощь приветствуется.

Answer 1

Давайте пройдемся по коду здесь на данный момент:

public void insert(E obj) 
{ 
    tree.add(tree.size(), obj); 
    siftUp(tree.size() - 1); 
} 

private void siftUp(int k) 
{ 
    E v = tree.get(k); 
    while (v.compareTo(tree.get(k/2)) == 1) 
    { 
     tree.add(k, tree.get(k/2)); 
     k = k/2; 
    } 
    tree.add(k, v); 
} 

Теперь вы делаете tree.insert(1), и все работает отлично. Затем вы вызываете tree.insert(0). Давай посмотрим что происходит.

• tree.add(tree.size(), obj) добавляет 0 в качестве следующего элемента в списке массивов. Так что теперь у вас есть список, содержащий [1, 0]
• код вызывает siftUp(1)
• в siftUp, первая строка получает элемент 1 из списка массива. На данный момент v = 1
• в операторе while, код сравнивает значение 1 со значением tree[k/2]. Начиная с k == 1, вы проверяете корневой узел (т. Е. tree[0]), который, как мы знаем, равен 1.
• Поскольку новое значение меньше его родительского, вы копируете родительское значение в позицию нового элемента. На данный момент список массивов содержит [1, 1].
• Вы делите ваш индекс, k, на 2, давая 0.
• Теперь вы возвращаетесь к состоянию while. k равно 0, а значение в tree[k] равно 1, что означает, что оно еще больше значения v.
• Теперь вы находитесь в бесконечном цикле, постоянно сравнивая значение с индексом 0 с вашим временным значением.

Проблема в том, что ваша петля не имеет определенного конечного состояния.

Один из способов решения проблемы состоит в том, чтобы закончить цикл, если k == 0.

private void siftUp(int k) 
{ 
    E v = tree.get(k); 
    while (k > 0 && v.compareTo(tree.get(k/2)) == 1) 
    { 
     tree.add(k, tree.get(k/2)); 
     k = k/2; 
    } 
    tree.add(k, v); 
} 

Следующая проблема, с которой вы столкнулись, заключается в неправильном вычислении родительского узла. Если корневой узел кучи имеет индекс 0, то для узла с индексом ix его левое дочернее устройство находится в (ix*2)+1, а правый ребенок - (ix*2)+2. Родитель узла находится в (ix-1)/2.

Рассмотрим кучу с тремя узлами:

 0 
     1 2 

Здесь номера узлов являются такими же, как индексы массива.

Если корень находится в индексе 0, то левый узел находится в точке (2 * 0) + 1. Правый узел находится в точке (2 * 0) + 2. Родитель 1 равен (1-1)/2. А родительский элемент 2 равен (2-1)/2. В вашем коде родительский расчет равен k/2, что даст неправильное значение 1 для узла с меткой 2 в куче выше.