英文:
How do Java Priority Queues Work Under The Hood?
问题
我似乎找不到任何信息来回答我的问题。因此，Java中的PriorityQueue是使用堆构建的。堆的插入和删除时间复杂度为O(logn)，因此如果我要进行堆排序，时间复杂度将为O(nlogn)。
但是，在创建堆时只需要O(n)的时间。所以假设我加入以下代码行
PriorityQueue<Character> heap = new PriorityQueue<>(list);
Java是在使用值构建数据结构，因此时间复杂度是O(n)，还是在之后插入，因此时间复杂度是O(nlogn)？
英文:
I cannot seem to find any information to answer my question. So Java PriorityQueue are built using heaps. Heaps have an insertion and deletion time of O(logn) so if I were to do a heap sort that would be O(nlogn).
But during creation of a heap it only takes O(n) time. So lets say I put the line
PriorityQueue<Character> heap = new PriorityQueue<>(list);
Is Java building the data structure with the values so its O(n) or is it inserting afterwards so its O(nlogn)?
答案1
得分: 1
你可以随时查看源代码：http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/PriorityQueue.java
当你从未排序的列表初始化它时，它会使用O(n)的heapify方法。
英文:
You can always check the source: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/PriorityQueue.java
When you initialize it from an unsorted list, it uses the O(n) heapify method.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论