深入探讨下java的PriorityQueue(pq)/TreeMap(tm)/TreeSet(ts)的时间复杂度

现在我能确定的是PQ的单次offer/poll都是Log n复杂度； TM，TS的put/get也是Log n的复杂度；给n个元素build一个PQ是O（n）复杂度。一下几个问题是我不太确定的，希望小伙伴们确定下：

• build一个pq（从无到有） n次所用时间为O（n），可以不可以说poll一个pq（size为n）一直到空也是O（n）复杂度呢？
• 对于TM和TS的一些遍历操作，复杂度又是多少呢？(看有人说是O（n）但是我没有找到确定答案。好像是因为遍历操作的时候并不是对这些数据结构直接操作，而且在一个pre-generated的view上面操作。)
  

• for (key : tm.keySet())
• for (value : tm.values())
• for (entry : tm.entrySet())
  

如果有确切的链接解释就更好了。谢谢！

从无到有build一个n的pq如果你是指一个一个offer进去是O(NlogN)吧 只有你用一个collection去init一个pq才是O(N) (heapify), 你一个一个poll出来 也是O(NlogN)

iiimisery 发表于 2019-4-2 12:56
从无到有build一个n的pq如果你是指一个一个offer进去是O(NlogN)吧 只有你用一个collection去init一个pq才是 ...

查了下没错 谢谢。其他问题有思路吗？

自问自答下，stackoverflow上面有两个相关的帖子1 2 都说是iterator是O(1)遍历的话就是O(n).

我不确定Java的pq是怎么实现的，可能是heap，楼主可以学一下heap的实现，make heap，heapify了解一下就知道了。你一个一个poll其实就是heap sort，时间复杂度nlogn

ts和tm的遍历本质上就是树的遍历，你想想看树的遍历复杂度