0

在下面的 replaceValue 方法中，我得到了一个索引越界异常，我不知道为什么。

[null, (10,4), (52,3), (39,9), (78,7), (63,8), (42,2), (50,411)]

重置值测试：411 size=7

[null, (10,4), (52,3), (39,9), (78,7), (63,8), (42,2), (50,101)]

去除测试：(10,4)

[null, (39,9), (52,3), (42,2), (78,7), (63,8), (50,101)]

大小=6

我尝试在这里再次替换该值并收到错误...

package heappriorityqueue;
import java.util.*;
public class HeapPriorityQueue<K,V> {
protected ArrayList<Entry<K,V>> heap;
protected Comparator<K> comp;
int size = 0;
protected static class MyEntry<K,V> implements Entry<K,V> {
    protected K key;
    protected V value;
    protected int loc;
    public MyEntry(K k, V v,int i) {key = k; value = v;loc =i;}
    public K getKey() {return key;}
    public V getValue() {return value;}
    public int getLoc(){return loc;}
    public String toString() {return "(" + key + "," + value + ")";}
    void setKey(K k1) {key = k1;}
    void setValue(V v1) {value = v1;}
    public void setLoc(int i) {loc = i;}
}
public HeapPriorityQueue() {
    heap = new ArrayList<Entry<K,V>>();
    heap.add(0,null);
    comp = new DefaultComparator<K>();
}
public HeapPriorityQueue(Comparator<K> c) {
    heap = new ArrayList<Entry<K,V>>();
    heap.add(0,null);
    comp = c;
}
public int size() {return size;}
public boolean isEmpty() {return size == 0; }
public Entry<K,V> min() throws EmptyPriorityQueueException {
    if (isEmpty())
        throw new EmptyPriorityQueueException("Priority Queue is Empty");
    return heap.get(1);
}
public Entry<K,V> insert(K k, V v) {
    size++;
    Entry<K,V> entry = new MyEntry<K,V>(k,v,size);
    heap.add(size,entry);
    upHeap(size);
    return entry;
}
public Entry<K,V> removeMin() throws EmptyPriorityQueueException {
    if (isEmpty())
        throw new EmptyPriorityQueueException("Priority Queue is Empty");
    if (size == 1)
        return heap.remove(1);
    Entry<K,V> min = heap.get(1);
    heap.set(1, heap.remove(size));
    size--;
    downHeap(1);
    return min;
}

public V replaceValue(Entry<K,V> e, V v) throws InvalidEntryException,
        EmptyPriorityQueueException {
// replace the value field of entry e in the priority
// queue with the given value v, and return the old value

This is where I am getting the IndexOutOfBounds exception, on heap.get(i);

if (isEmpty()){
        throw new EmptyPriorityQueueException("Priority Queue is Empty.");
    }
    checkEntry(e);
    int i = e.getLoc();
    Entry<K,V> entry=heap.get(((i)));
    V oldVal = entry.getValue();
    K key=entry.getKey();
    Entry<K,V> insert = new MyEntry<K,V>(key,v,i);
    heap.set(i, insert);
    return oldVal;
}

public K replaceKey(Entry<K,V> e, K k) throws InvalidEntryException,
        EmptyPriorityQueueException, InvalidKeyException {
    // replace the key field of entry e in the priority
    // queue with the given key k, and return the old key
    if (isEmpty()){
        throw new EmptyPriorityQueueException("Priority Queue is Empty.");
    }
    checkKey(k);
    checkEntry(e);
    K oldKey=e.getKey();
    int i = e.getLoc();
    Entry<K,V> entry = new MyEntry<K,V>(k,e.getValue(),i);
    heap.set(i,entry);
    downHeap(i);
    upHeap(i);
    return oldKey;
}

public Entry<K,V> remove(Entry<K,V> e) throws InvalidEntryException,
        EmptyPriorityQueueException{
    // remove entry e from priority queue and return it
    if (isEmpty()){
        throw new EmptyPriorityQueueException("Priority Queue is Empty.");
    }
    MyEntry<K,V> entry = checkEntry(e);
    if (size==1){
        return heap.remove(size--);
    }
    int i = e.getLoc();
    heap.set(i, heap.remove(size--));
    downHeap(i);
    return entry;
}

protected void upHeap(int i) {
    while (i > 1) {
        if (comp.compare(heap.get(i/2).getKey(), heap.get(i).getKey()) <= 0)
            break;
        swap(i/2,i);
        i = i/2;
    }
}
protected void downHeap(int i) {
    int smallerChild;
    while (size >= 2*i) {
        smallerChild = 2*i;
        if ( size >= 2*i + 1)
            if (comp.compare(heap.get(2*i + 1).getKey(), heap.get(2*i).getKey()) < 0)
                smallerChild = 2*i+1;
        if (comp.compare(heap.get(i).getKey(), heap.get(smallerChild).getKey()) <= 0)
            break;
        swap(i, smallerChild);
        i = smallerChild;
    }
}
protected void swap(int j, int i) {
    heap.get(j).setLoc(i);
    heap.get(i).setLoc(j);
    Entry<K,V> temp;
    temp = heap.get(j);
    heap.set(j, heap.get(i));
    heap.set(i, temp);

}
public String toString() {
    return heap.toString();
}
protected MyEntry<K,V> checkEntry(Entry<K,V> ent) 
    throws InvalidEntryException 
  {
    if(ent == null || !(ent instanceof MyEntry))
      throw new InvalidEntryException("Invalid entry.");
    return (MyEntry)ent;
  }
protected void checkKey(K key) throws InvalidKeyException{
    try{comp.compare(key,key);}
    catch(Exception e){throw new InvalidKeyException("Invalid key.");}
}

}

HeapPriorityQueue<Integer,Integer> testPQ = new HeapPriorityQueue<Integer,Integer>();
    System.out.print("[");
    int x;
    for (int i = 0; i < 10; i++) {
        x = (int) (100 * Math.random());
        System.out.print(" " + x);
        testPQ.insert(x,i);


    }
    System.out.println("]");

    System.out.println(testPQ);
    for (int i = 0; i < 5; i++) {
        System.out.println(testPQ.removeMin());
        System.out.println(testPQ);
    }

    Entry e = testPQ.insert(10, 4);
    System.out.println("insertion of "+e);
    System.out.println(testPQ);
    System.out.println("size="+testPQ.size);
    System.out.println(e.getKey());
    Entry r = testPQ.insert(50, 411);
    System.out.println("insertion of "+r);

    System.out.println("size="+testPQ.size);
    System.out.println(testPQ);
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 101));

    System.out.println("size="+testPQ.size);
    System.out.println(testPQ);
    System.out.println("removal test:"+testPQ.remove(e));
    System.out.println(testPQ);
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 201));
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 301));
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 401));
    System.out.println("size="+testPQ.size);
    System.out.println(testPQ);

    Entry k = testPQ.min();
    System.out.println("replacement key test:"+testPQ.replaceKey(k,77)
            +" w/77");
    System.out.println(testPQ);
    Entry v = testPQ.min();
    System.out.println("replacement key test:"+testPQ.replaceKey(v,6)+
            " w/6");
    System.out.println(testPQ);
    System.out.println("removal test:"+testPQ.remove(v));
    System.out.println(testPQ);

run:
[ 17 86 13 52 98 4 9 25 6 75]
[null, (4,5), (6,8), (9,6), (25,7), (75,9), (17,0), (13,2), (86,1), (52,3), (98,4)]
(4,5)
[null, (6,8), (25,7), (9,6), (52,3), (75,9), (17,0), (13,2), (86,1), (98,4)]
(6,8)
[null, (9,6), (25,7), (13,2), (52,3), (75,9), (17,0), (98,4), (86,1)]
(9,6)
[null, (13,2), (25,7), (17,0), (52,3), (75,9), (86,1), (98,4)]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 7, Size: 7
(13,2)
[null, (17,0), (25,7), (86,1), (52,3), (75,9), (98,4)]
(17,0)
[null, (25,7), (52,3), (86,1), (98,4), (75,9)]
insertion of (10,4)
[null, (10,4), (52,3), (25,7), (98,4), (75,9), (86,1)]
size=6
10
insertion of (50,411)
size=7
[null, (10,4), (52,3), (25,7), (98,4), (75,9), (86,1), (50,411)]
replacement value test411
size=7
[null, (10,4), (52,3), (25,7), (98,4), (75,9), (86,1), (50,101)]
removal test:(10,4)
[null, (25,7), (52,3), (50,101), (98,4), (75,9), (86,1)]
at java.util.ArrayList.rangeCheck(ArrayList.java:604)
at java.util.ArrayList.get(ArrayList.java:382)
at heappriorityqueue.HeapPriorityQueue.replaceValue(HeapPriorityQueue.java:283)
at heappriorityqueue.Main.main(Main.java:55)

Java 结果：1 构建成功（总时间：0 秒）

4

1 回答 1

1

您将条目的数组索引保存在条目本身中。但是在你的remove()方法中你不会改变它。您必须更改所有更改位置的元素的索引，否则您将在进一步的删除调用中删除错误的元素。

在您的示例(50,101)中，最初的索引为 6。此值在删除后保留，因此如果您尝试替换它，它仍会尝试访问int i = e.getLoc();不再存在的索引 6（因为 ）。

于 2012-11-25T11:15:29.267 回答