使用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最后写一个方法，对堆中的每个元素执行上面的方法，并且工作。这不是一个优雅的解决方案，但它完成了工作。