java – Priority Queue poll()时间复杂度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – Priority Queue poll()时间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含620字，纯文字阅读大概需要1分钟。

内容图文

鉴于以下代码：

pq.offer(x);
pq.poll();

对于第一行代码,元素x被插入到优先级队列pq中,商品的时间复杂度是log(k),其中k是pq的大小.

那么我的问题是,对于紧跟在第一行之后的第二行代码,poll()的时间复杂度是多少？

在第一行提供之后,pq已经被排序了,所以poll只是检索并删除队列的头部,那么我认为它应该是O(1),对吗？

谢谢

解决方法:

根据PriorityQueue#poll的源代码,似乎操作是O(log n)：

@SuppressWarnings("unchecked")
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

这是因为siftDown是O(log n),因为PriorityQueue中的数据被存储为堆.

内容总结

以上是互联网集市为您收集整理的java – Priority Queue poll()时间复杂度全部内容，希望文章能够帮你解决java – Priority Queue poll()时间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端