java priorityQueue poll()方法的大O是什么
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19718145/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is big O of java priorityQueue poll() method
提问by user2547667
I checked http://en.wikipedia.org/wiki/Priority_queueit said Naive implementations is o(n).
我检查了http://en.wikipedia.org/wiki/Priority_queue它说 Naive 实现是 o(n)。
If I use binary search, it will be log(n). But I am not sure if it is used in Java. And how do I use binary search on a priorityQueue?
如果我使用二进制搜索，它将是 log(n)。但我不确定它是否在 Java 中使用。以及如何在 priorityQueue 上使用二分搜索？
Thanks.
谢谢。
采纳答案by tom
From the PriorityQueue Javadoc:
Implementation note: this implementation provides O(log(n))time for the enqueing and dequeing methods (
offer,poll,remove()andadd); linear time for theremove(Object)andcontains(Object)methods; and constant time for the retrieval methods (peek,element, andsize).
实现说明：该实现为入队和出队方法（、、和 ）提供了O(log(n))时间；和 方法的线性时间；和恒定时间检索方法（， ，和）。
offerpollremove()addremove(Object)contains(Object)peekelementsize
Priority queues are typically implemented using a heap. If implemented as a sorted array, the head can be looked up and removed in O(1) since it is always the last element*, but inserting new elements is O(n) since the insertion point needs to be found (which could be done in O(log(n)) using a binary search) and then all the later elements need to be shifted to make room, which is O(n).
优先级队列通常使用堆实现。如果实现为排序数组，则可以在 O(1) 中查找并删除头部，因为它始终是最后一个元素*，但插入新元素是 O(n)，因为需要找到插入点（这可能是使用二进制搜索在 O(log(n)) 中完成)，然后所有后面的元素都需要移动以腾出空间，即 O(n)。
* Assuming the head is the smallest element and the array is sorted in descending order.
* 假设头部为最小元素，数组按降序排列。
