堆优先级队列实现

我正在处理一个涉及堆实现的代码，我似乎在我的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; 
    } 


}

来源

2014-12-02 RK1995

大概一旦交换元素，parent(index)的结果将会改变。尝试

protected void bubbleUp() { 
    int index = this.currentSize; 
    int pi; 
    while((pi = parent(index)).compareTo(storage[index]) > 0) { 
     swapElement(index, pi); 
     index = pi; 
    } 
}

来源

2014-12-02 04:43:31

堆优先级队列实现

回答

相关问题