優先級隊列，可比

我必須寫一個priotity queye爲實現如下因素接口：優先級隊列，可比

public interface PQueue<T extends Comparable<T>> { 
    public void insert(T o); // inserts o into the queue 
    public T remove();   // removes object with highest priority (by natural order) 
}

我會很高興一些幫助和線索，becouse我甚至不知道如何與這個開始問題。

來源

2010-10-08 Devel

http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html？ – kennytm 2010-10-08 18:48:40

作業嗎？ – 2010-10-08 18:50:05

證明你已經做出了一些努力。在線或在教科書上閱讀優先隊列，然後向我們展示您的嘗試。 – 2010-10-08 18:51:54

我會從這樣的事情開始。總的想法是，你有一個內部列表，當你插入一個新的項目，你做了二進制搜索，以找到它在該列表中的屬性。這樣，你的內部列表總是被排序，所以當你調用remove（）時，你只需要最後一個（或第一個取決於你如何訂購東西）項目。

聲明：這應該被視爲僞代碼。我知道有一個事實，它有問題。這只是一個起點。

public class PQueueImpl<T> implements PQueue<T> { 
    private List<T> internalQueue; 

    public void insert(T item){ 
     int insertionPoint = Collections.binarySearch(internalQueue, item); 
     internalQueue.add(insertionPoint, item); 
    } 

    public T remove(){ 
     return internalQueue.remove(internalQueue.size() - 1); 
    } 
}

來源

2010-10-08 18:58:25

您可以查看java.util.PriorityQueue的源代碼。它們的實現由一個Object數組支持，並且比我給出的另一個示例複雜得多，但我相信它的工作原理和性能也要好得多。

來源

2010-10-08 19:01:40

優先級隊列在實踐中實際上被實施爲heaps。它們也可以實現爲平衡的binary search tree或任何其他快速排序的數據結構。關鍵是數據結構必須非常快（比O（n））最大/最小速度更快，插入，刪除和更新操作。

來源

2010-10-08 19:09:54 MAK

優先級隊列，可比

回答

相關問題