최소 힙을 사용하여 우선 순위 큐 구현

Question

최소 힙을 사용하여 우선 순위 큐를 구현하려고하는데 개체가 잘못된 순서로 큐에서 나옵니다. 내 직관은 문제가 대기열에서 위 또는 아래로 이동하는 내 방법과 관련되어 있음을 알지만 문제가 어디에 있는지 알 수 없습니다. 누군가 내 알고리즘을보고 즉시 잘못되는 것이 있는지 확인할 수 있습니까? 미리 감사드립니다.

private void walkDown(int i) { 

    if (outOfBounds(i)) 
    { 
     throw new IndexOutOfBoundsException("Index not in heap : " + i); 
    } 

    int current = i; 
    boolean right; 
    Customer temp = this.heap[i]; 

    while (current < (this.size >>> 1)) 
    { 

     right = false; 

     if (right(current) < this.size && 
       this.comparator.compare(this.heap[left(current)], 
         this.heap[right(current)]) > 0) 
     { 
      right = true; 
     } 


     if (this.comparator.compare(temp, right ? this.heap[right(current)] 
       : this.heap[left(current)]) < 0) 
     { 
      break; 
     } 

     current = right ? right(current) : left(current); 
     this.heap[parent(current)] = this.heap[current]; 

    } 

    this.heap[current] = temp; 

} 

까지 선별 방법 :

는

private void walkUp(int i) { 

    if (outOfBounds(i)) 
    { 
     throw new IndexOutOfBoundsException("Index not in heap : " + i); 
    } 

    int current = i; 
    Customer temp = this.heap[i]; 

    while (current > 0) 
    {   
     if (this.comparator.compare(this.heap[current], 
        this.heap[parent(current)]) >= 0) 
     { 
      break; 
     } 

     this.heap[current] = this.heap[parent(current)]; 
     current = parent(current); 

    } 

    this.heap[current] = temp; 

} 

EDIT :

(가)에있어서 비교는 다음과 같이 정의되어 다음과

여기

아래쪽 선별을위한 방법

 @Override 
     public int compare(Customer cust1, Customer cust2) { 

      return cust1.priority() - cust2.priority(); 

     } 

Answer 1

나는 ende 위에서 힙의 모든 요소에 대해 위의 메서드를 실행하는 메서드를 작성하면됩니다. 그것은 우아한 해결책은 아니지만 업무가 완료됩니다.