힙 우선 순위 대기열 구현

Question

힙 구현이 관련된 코드를 작업하고 내 while 루프 줄 내 bubbleUp 메서드에서 dereferenced 오류를 받고있는 것 같습니다. 이는 다소 기본적인 질문 일 수 있지만이를 해결하는 가장 좋은 방법은 무엇입니까? 또한 큐에서 가장 높은 요소를 제거하기 위해 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; 
    } 


} 

Answer 1

아마도, parent(index)의 결과가 변경됩니다. 시도해보십시오.

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