44

remove()Java 中 Priority Queue 类上的函数的复杂性（大哦）是多少？我在任何地方都找不到任何文档，我认为它是 O(n)，考虑到您必须在删除它之前找到该元素，然后重新调整树。但我看到其他人不同意并认为这是 O(logn)。有任何想法吗？

4

4 回答 4

52

混乱实际上是由您的“删除”功能引起的。在java中，有两个remove函数。

  1. remove() -> 这是删除头/根，需要 O(logN) 时间。

  2. remove(Object o) -> 这是删除任意对象。找到这个对象需要 O(N) 时间，删除它需要 O(logN) 时间。

于 2016-08-23T04:54:24.907 回答
39

remove 的复杂度是 O(N)，因为 contains 的复杂度是 O(N)（在 java 的优先级队列类中）

在您自己的优先级队列实现中，可以将其设为 O(logN) 的一种方法是维护一个辅助数据结构，如 HashMap，它维护从优先级队列中的值到其在队列中的位置的映射。因此，在任何给定时间 - 您都会知道任何值的索引位置。

请注意，此修改不会影响任何现有操作的运行时间 - 您只需要在 heapify 操作期间更新映射。

于 2014-02-28T05:29:42.933 回答
10

根据 Oracle 文档：“实现说明：此实现为入队和出队方法（offer、poll、remove()和 add）提供O(log(n))时间；remove(Object) 和 contains(Object) 的线性时间) 方法；以及检索方法（peek、元素和大小）的恒定时间。”

在此处链接到 Oracle 文档

于 2015-09-22T12:03:55.657 回答
0

请检查： http ://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

“此实现为入队和出队方法（offer、poll、remove() 和 add）提供 O(log(n)) 时间；为 remove(Object) 和 contains(Object) 方法提供线性时间”

因此对于 poll() 和 remove()，那个 log(N) 但是对于 remove(object)，那个 log(N)

于 2021-08-08T18:33:38.167 回答