Java優先級隊列接口實現

這是幾天前我在面試中被問到的問題，我對這種方法並不確定。建議將高度讚賞：Java優先級隊列接口實現

我怎麼能實現Queue接口獲得隊列（）方法在O（1）和出隊（）在O（n）的方法。

我怎麼能實現Queue接口獲得隊列（）方法在O（n）和出隊（）方法在O（1）。

謝謝。

來源

2010-07-24 Rachel

這是一個棘手的問題，希望的位置是一個有信譽的一個。 – mdma 2010-07-24 00:13:02

嗯......我以爲是。 – Rachel 2010-07-24 00:20:11

@mdma - 你在開玩笑嗎？或者你真的認爲你的評論。 – Rachel 2010-07-25 13:03:46

一個典型的PriorityQueue實現將使用堆以獲取「添加」操作O（LG n）性能，所以O（n）性能會更容易。

例如，你可以使用一個載體或鏈表作爲底層數據結構。對於O（1）「添加」，您可以簡單地將新值添加到末尾，對於O（n）「移除」，您可以對最小值進行線性搜索。相反，對於O（n）「添加」，您可以執行線性掃描以查找下一個最大值，然後插入它，對於O（1）刪除，您可以簡單地刪除列表的第一個元素。

來源

2010-07-24 00:15:48 maerics

對於O（1）的方式來你必須保持跟蹤你的隊列的最後一個元素，讓您可以輕鬆地多了一個附加後，您的隊列無論大小隊列（）方法。

對於queue（）中的O（n）和dequeue（）中的O（1），您需要跟蹤變量中隊列的第一個元素，以便不管內部元素的數量如何可以通過一組指令（不重複）從列表中刪除第一個。

在每個兩種情況下你只需要添加一個額外的變量到類。

來源

2010-07-24 00:15:57

你能給出一個相同的代碼示例嗎？這裏很難理解。 – Rachel 2010-07-24 00:20:43

嗯，我現在還沒有一個方便的方法，但是通過使用節點來實現自己創建的Java PriorityQueue，您可以輕鬆實現這一目標。製作節點類，其中節點是具有對象的實體，並且是對下一個節點的引用。然後創建一個列表，它獲得了第一個節點/最後一個節點的引用[取決於您是否希望O（1）用於排隊或出隊或兩者]，然後完成！我不知道核心Java的PriorityQueue類是如何實現的，但它也可能以這種方式或類似的方式實現。檢查源代碼可能會成爲一個例子。 – 2010-07-24 00:37:57

只要看一看：

http://www.docjar.com/html/api/java/util/PriorityQueue.java.html

請記住，所有優秀的程序員複製好的代碼：P

我假設你有關於數據結構，列表，地圖等基本的瞭解如果你不知道，理解這項工作如何沒有多大意義，那就去進一步調查一下這個問題。

來源

2010-07-24 00:16:18

隊列（）在O法（1）的O型出隊（）方法（N）：

使用鏈表，乾脆直接在隊列中每增加一個新條目列表的頭（）。在dequeue（）中迭代列表並刪除並返回具有最高優先級的條目。

隊列（）中O的方法（n）和出隊（）中O的方法（1）：

再次使用一個鏈表。但是這次在queue（）中迭代條目以將新條目放入其優先排序位置（實際上這是插入排序的一個步驟）。在dequeue（）中，您現在可以始終刪除並返回列表的第一個元素。

來源

2010-07-24 00:20:05 x4u