java - Java 优先级队列

Question

Java 的优先级队列是一种数据结构，O(log n)对于 put（插入）和O(log n)poll（检索和删除 min 元素）具有复杂性。

C++ STL 的多重映射具有相同的功能，但O(1)在检索和删除最小元素（开始和擦除）方面很复杂。Java中是否有等价物？

Answer 1

试试Apache Commons Collections。

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

实际上那里也有一个Priority Queue，但它被贬值了，有利于buffer package。

Answer 2

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

Answer 3

首先，我会检查 C++ 的 multimap 是否确实给出了 O(1) 来删除min 元素。最常见的映射/优先级队列结构是树结构，其中查询最小元素具有 O(1) 复杂度，但删除它是 O(log n)。

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

PS忘了说：看看ConcurrentSkipListMap.pollFirstEntry()。

Answer 4

std:multimap将是一个树结构，这意味着一起添加和删除将是 O(log n)。