Java优先级队列

Question

Java的优先级队列是用于put（插入）的 O（log n）复杂度的数据结构，以及用于poll（检索和删除min元素）的 O（log n）的数据结构。

C ++ STL的 multimap 具有相同的功能，但 O（ 1）检索和删除min元素（开始和擦除）的复杂性。 Java中是否有等价物？

Answer 1

Google Collections 提供了Multimap实施。具体来说，TreeMultimap可以使用比较器根据键，值或两者进行排序。

Answer 2

尝试 Apache Commons Collections

MultiHashMap和MultiValueMap（从该页面链接）实际上实现了接口。

实际上有一个优先级队列也在那里，但它的折旧有利于缓冲包。

Answer 3

首先，我要检查C ++的multimap是否确实为删除 min元素提供了O（1）。 sotred maps / priority队列最常见的结构是树结构，其中查询 min元素具有O（1）复杂度，但 remove 它是O（log n）。

那就是说，我认为跳过列表（由Java的 ConcurrentSkipListMap 实现）可能给你O（1）删除最小元素，但是我我不是很确定。评估ConcurrentSkipListMap的性能时的一个问题是遍历操作“整理”。先前删除留下的标记。因此，操作的复杂性实际上取决于先前的操作。 （另一方面，在某种程度上，几乎任何算法都是如此：CPU高速缓存中的某些数据是否可以取决于先前的操作是否将其放在那里......）

P.S。忘了说：看看 ConcurrentSkipListMap.pollFirstEntry（）。

Answer 4

std：multimap 将是一个树形结构，这意味着一起添加和删除将是O（log n）。