什麼是java的priorityOne poll（）方法的大O O

我查過http://en.wikipedia.org/wiki/Priority_queue 它說樸素的實現是o（n）。什麼是java的priorityOne poll（）方法的大O O

如果我使用二進制搜索，它將是log（n）。但我不確定它是否在Java中使用。如何在priorityQueue上使用二進制搜索？

謝謝。

2013-10-31 user2547667

你只是在問關於Java的'poll'的實現嗎？ [閱讀源代碼]（http://grepcode.com）[沒有替代品]（http://www.codinghorror.com/blog/2012/04/learn-to-read-the-source-luke.html） /file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/PriorityQueue.java#line-531）。當然，[標準文檔]（http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html）已經回答了這個特定的問題。 –

由於很好的原因，PriorityQueues通常使用基於堆的實現。所以Java的確如此。 –

從PriorityQueue Javadoc：

實現注意事項：此實現提供O（日誌（n））的時間的和入隊方法dequeing（offer，poll，remove()和 add）;線性時間爲remove(Object)和contains(Object) 方法;和檢索方法的恆定時間（peek, element和size）。

優先級隊列通常使用heap實現。如果作爲一個有序數組實現，頭可以在O（1）中被查找和移除，因爲它總是最後一個元素*，但是插入新元素是O（n），因爲需要找到插入點（可能是在O（log（n））中使用二進制搜索完成），然後所有後面的元素需要移位以騰出空間，即O（n）。

^{*假設頭是最小的元素，並且數組按降序排序。}

來源

2013-10-31 23:12:12 tom

什麼是java的priorityOne poll（）方法的大O O

回答

相關問題