优先级队列消除了复杂性时间
2022-09-01 00:24:35
Java 中优先级队列类上的函数的复杂性（大 oh）是多少？我无法在任何地方找到任何记录的内容，我认为它是O（n），考虑到您必须在删除它之前找到该元素，然后重新洗牌树。但我看到其他人不同意并认为这是O（logn）。有什么想法吗？remove()
答案 1
这种混乱实际上是由您的“删除”功能引起的。在java中，有两个删除函数。
remove（） -> 这是为了删除头/根，它需要O（logN）时间。
remove（Object o） -> 这是为了删除任意对象。找到此对象需要 O（N） 时间，删除它需要 O（logN） 时间。
答案 2
删除的复杂性是 O（N），因为 contains 的复杂性是 O（N）（在 java 的优先级队列类中）
在您自己的优先级队列实现中，可以将其设置为O（logN）的一种方法是维护一个辅助数据结构，例如HashMap，该结构维护从优先级队列中的值到其在队列中的位置的映射。因此，在任何给定时间 - 您将知道任何值的索引位置。
请注意，此修改不会影响任何现有操作的运行时间 - 您只需要在堆操作期间更新映射。
推荐
