1
我正在處理一個涉及堆實現的代碼,我似乎在我的while循環行中在我的bubbleUp方法中得到一個解除引用的錯誤。這可能是一個相當基本的問題,但解決這個問題的最好方法是什麼?我在執行removeHigh方法時也遇到了一些麻煩,這是爲了從隊列中移除最高的元素。堆優先級隊列實現
public class HeapPriorityQueue implements PriorityQueue
{
protected final static int DEFAULT_SIZE = 10000;
protected Comparable[] storage;
protected int currentSize;
public HeapPriorityQueue()
{
this.storage=new Comparable[DEFAULT_SIZE];
this.currentSize=0;
}
public HeapPriorityQueue(int size)
{
this.currentSize=size;
this.storage=new Comparable[currentSize];
}
public int size()
{
return currentSize;
}
public boolean isEmpty ()
{
if(currentSize==0)
return true;
else
return false;
}
public boolean isFull ()
{
if(currentSize==DEFAULT_SIZE)
return true;
else
return false;
}
public Comparable removeHigh() throws HeapEmptyException
{
if(isEmpty()) {
throw new HeapEmptyException();
}else{
Comparable[] k = new Comparable[0];
k.equals(storage[1]);
storage[1] = storage[currentSize];
storage[currentSize] = null;
currentSize--;
bubbleDown();
return storage[currentSize];
}
}
public void insert (Comparable k ) throws HeapFullException
{
if(isFull()) {
throw new HeapFullException();
}
currentSize++;
int index = currentSize;
storage[index] = k;
bubbleUp();
}
protected void bubbleUp ()
{
int index = this.currentSize;
while(parent(index).compareTo(storage[index]) > 0) {
swapElement(index, parent(index));
index = parent(index);
}
}
protected void bubbleDown()
{
int index = 1;
while (hasLeft(index)) {
int smaller = leftChild(index);
if(hasRight(index) &&
storage[leftChild(index)].compareTo(storage[rightChild(index)])>0) {
smaller = rightChild(index);
}
if(storage[index].compareTo(storage[smaller]) > 0) {
swapElement(index, smaller);
}else{
break;
}
}
}
protected void swapElement (int p1, int p2)
{
Comparable k = storage[p1];
storage[p1] = storage[p2];
storage[p2] = k;
}
protected int parent (int pos)
{
if(pos>1)
return pos;
else
return 0;
}
protected int leftChild (int pos)
{
return pos*2;
}
protected int rightChild (int pos)
{
return pos*2+1;
}
protected boolean hasLeft (int pos)
{
if(leftChild(pos) <= currentSize)
return true;
else
return false;
}
protected boolean hasRight (int pos)
{
if(rightChild(pos) <= currentSize)
return true;
else
return false;
}
}