algorithm - 高效存储对象，允许快速访问最高值( HashMap 与优先级队列)

Question

所以我有一组对象 X，每个对象都有一个值 v[x]。

如何以允许我有效计算具有最高值的 x 的方式存储对象 X？

我还希望能够更改 v[x] 的值，并让 x 自动落到数据结构中的正确位置。

我考虑过为此使用优先级队列，但我的 friend 告诉我我应该改用 HashMap 。这让我感到困惑，因为 HashMap 是无序的。

Answer 1

你是对的，你的 friend 是错的:散列映射是行不通的，因为它是无序的。如果您希望在对象 x 的外部维护值 v，则 HashMap 可能很有用，但是除了提供排序的数据结构之外，它还需要一个单独的数据结构.

带有比较器的优先级队列比较附加到对象 x 的值 v 将为您提供一种快速获取具有最高值的对象的方法。

无论您要使用什么数据结构，当值 v[x] 更改时，您都可以自行更新它。通常，您需要从结构中删除对象，然后立即将其插入，以便根据更新后的值将其放置在新位置。