使用min堆實現優先級隊列

Question

我正在嘗試使用minheap實現優先級隊列，但我的對象以錯誤的順序從隊列中走出來。我的直覺告訴我，我的方法是在隊列中上下篩選，但我無法看到問題出在哪裏。有人可以看看我的算法，看看有什麼不對嗎？先謝謝你。

這裏是篩分下來方法：

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; 

} 

編輯：

的比較方法被定義如下：

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

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

     } 

Answer 1

I ende最後寫一個方法，對堆中的每個元素執行上面的方法，並且工作。這不是一個優雅的解決方案，但它完成了工作。