在Java中出隊的優先級隊列問題

Question

嗨，所以即時在項目上工作，我的出隊最小值首先似乎有問題。它似乎入列罰款。在20,15,11,29中打出正確的11,20,15,29。這些數字符合要達到的期限。現在，當我想取出最高值時，它會抓取11個需要的操作，並放棄截止日期爲11的任務。然後，當我抓取下一個頂部值時，返回20而不是15。爲什麼？任何幫助將不勝感激！

import java.util.Comparator; 


public class treeCompare implements Comparator<Task> { 

    public int compare(Task t1, Task t2) { 

     int dead1 = t1.getDeadline(); 
     int dead2 = t2.getDeadline(); 

     return dead1 - dead2; 

    } 


} 

    import java.util.ArrayList; 
import java.util.Comparator; 


public class PriorityQueue<E> implements QueueADT<E> { 

    private ArrayList<E> items; 
    private int max; 
    private Comparator<E> comp; 

    public PriorityQueue(Comparator<E> comp, int maxCapacity){ 
     this.comp = comp; 
     this.max = maxCapacity; 
     items = new ArrayList<E>(); 
    } 



    public boolean isFull() { 
     if(size() == max) return true; 
     else return false; 
    } 


    private void siftUp() { 
      int k = items.size() - 1; 
      while (k > 0) { 
       int p = (k-1)/2; 
       E item = items.get(k); 
       E parent = items.get(p); 

        if (comp.compare(items.get(k), items.get(p)) < 0) { 
         // swap 
         items.set(k, parent); 
         items.set(p, item); 

         // move up one level 
         k = p; 

       } else { 
        break; 
       } 
      } 
     } 

     public void enqueue(E item)throws FullQueueException { 
      if(isFull()) throw new FullQueueException(); 
      items.add(item); 
      siftUp(); 
     } 


    /** 
    * Returns the front item of the queue without removing it. 
    * @return the front item of the queue 
    * @throws EmptyQueueException 
    */ 
    public E peek() throws EmptyQueueException { 
     if(isEmpty()) throw new EmptyQueueException(); 
     else{ 
      E item = items.get(0); 
      return item; 
     } 
    } 

    private void siftDown() { 
     int k = 0; 
     int l = 2*k+1; 
     while (l < items.size()) { 
      int max=l, r=l+1; 
      if (r < items.size()) { // there is a right child 
       if (comp.compare(items.get(r), items.get(l)) > 0) { 
        max++; 
       } 
      } 
      if (comp.compare(items.get(k), items.get(max)) > 0) { 
        // switch 
        E temp = items.get(k); 
        items.set(k, items.get(max)); 
        items.set(max, temp); 
        k = max; 
        l = 2*k+1; 
      } else { 
       break; 
      } 
     } 
    } 

    public E dequeue() throws EmptyQueueException { 
     if (items.size() == 0) { 
      throw new EmptyQueueException(); 
     } 
     if (items.size() == 1) { 
      return items.remove(0); 
     } 
     E hold = items.get(0); 
     items.set(0, items.remove(items.size()-1)); 
     siftDown(); 
     return hold; 
    } 

    public int size() { 
     return items.size(); 
    } 

    public boolean isEmpty() { 
     return items.isEmpty(); 

    } 



    public String toString() { 
     return items.toString(); 
    } 


    public int capacity() { 
     return max; 
    } 

} 

Answer 1

的對比comp.compare(items.get(r), items.get(l)) > 0在shiftDown()似乎被顛倒。

反轉它（並且爲了清晰起見而重命名變量max）算法似乎工作（據我測試）。

private void siftDown() { 
     int k = 0; 
     int l = 2*k+1; 
     while (l < items.size()) { 
      int min=l, r=l+1; 
      if (r < items.size()) { // there is a right child 
       if (comp.compare(items.get(r), items.get(l)) < 0) { 
        min = r; 
       } 
      } 
      if (comp.compare(items.get(k), items.get(min)) > 0) { 
        // switch 
        E temp = items.get(k); 
        items.set(k, items.get(min)); 
        items.set(min, temp); 
        k = min; 
        l = 2*k+1; 
      } else { 
       break; 
      } 
     } 
    } 

如果我插入[20，15，11，1，29，10，7，28，3，54，40，34，58]我檢索[1，3，7，10，11， 15,20,28,29,34,40,54,58]，看起來不錯。
希望它有幫助！