优先级队列消除了复杂性时间
Java中Priority Queue类的remove()函数的复杂性（大哦）是多少？ 我无法在任何地方找到任何记录，我认为它是O（n），考虑到你必须在删除它之前找到该元素然后重新洗牌。 但我看到其他人不同意并认为它是O（logn）。 有任何想法吗？
这种混淆实际上是由你的“删除”function引起的。 在java中，有两个删除函数。
-
remove（） – >这是删除头/根，需要O（logN）时间。
-
remove（Object o） – >这是删除任意对象。 查找此对象需要O（N）时间，删除它需要O（logN）时间。
删除的复杂性是O（N），因为contains的复杂性是O（N）（在java的优先级队列类中）
在您自己的优先级队列实现中，O（logN）的一种方法是维护一个辅助数据结构，如HashMap，它维护从优先级队列中的值到其在队列中的位置的映射。 因此，在任何给定时间 – 您将知道任何值的索引位置。
请注意，此修改不会影响任何现有操作的运行时间 – 您只需要在heapify操作期间更新映射。
根据Oracle文档：“实现说明：此实现为排队和出队方法提供O（log（n））时间（offer，poll， remove（）和add）; remove（Object）和contains（Object）的线性时间）方法;以及检索方法的持续时间（peek，element和size）。“
链接到Oracle Doc