java - 实现一个没有任何数组列表的堆

Question

我的插入方法有问题。当我去添加一个需要交换的数字时，我得到一个索引越界异常。这里： Collections.swap(table, table.get(parent), table.get(child)); 这就是我添加到堆中的方式。tHeap.insert(14); 谢谢你的帮助。

    public class Heap {
private ArrayList<Integer> table;

public Heap() {
    table = new ArrayList<Integer>();
}

public void insert(Integer toInsert) {
    table.add(toInsert);
    int child = table.size() - 1;
    int parent = (child - 1) / 2;
    //TextIO.putln("1  " + parent + " " + toInsert + " " + child);
    while (parent >= 0 && table.get(parent) > table.get(child)) {
        TextIO.putln("Swapping: " + parent + " Parent for Child: " + child);
        Collections.swap(table, table.get(parent), table.get(child));
    }

}

public void printTable() {
    for (int i = 0; i < table.size(); i++) {
        TextIO.putln("Index: " + i + " Data: " + table.get(i));

    }

}
    }

Answer 1

I think you mean Collections.swap(table, parent, child);? ArrayList.get will return the element at an index (Java ArrayList API) Collections.swap swaps the elements at an index (Java Collections API). You want to be passing in the indices, not the values at the indices. Also I think in your while loop you may want to be updating child and parent.