具有快速随机访问的堆状数据结构？

Question

我的情况是这样的：

• 我有实体的集合，每个都有一个“善”属性。
• 我希望一次抓一个实体，从“最好”到“最差”。
• 在获得“最佳”实体后，我的其他实体中的几个（相对较少）实体的“善”属性会发生变化，而且这一变化必须纳入我即将决定的下一个“最佳”实体中。
• 一些（相对较少的）实体在抓取后可能变得“毫无价值”，这些应该从我的收藏中删除。
• 由于我刚刚抓住的实体很容易构造出一组现在“脏”的对象，也就是说，这组实体可能具有与现在不同的“优点”，或者已经成为“不务正业”。

所以，我需要的数据结构，让我：

• 迅速抢占一个集合的“最大”（如，一个最大堆）。
• 快速更新我的集合中对象的基础排序以适应上述情况。 （如果我们可以在底层堆实现中访问脏对象的位置（例如数组索引），那么在堆中很容易做到。）
• 有保证我的集合中的条目之间没有冲突。 （这些条目是对上述实体的引用。）

我的想法是将max-heap与无序映射一起使用，键入堆条目，并且值等于，例如，堆实现中底层数组中对象的各个索引。

我想知道的是，是否可能有一个更适合这种情况的数据结构。

Answer 1

如果在抓取最佳实体时很少有成员受到影响，那么您可以通过使用链表和无序映射（每个都有原始实体集合）以及最大堆来改进运行时。从链表最后删除最佳实体后，您将使用映射来查找受影响的实体，将它们从列表中删除并将非无价值的实体添加到最大堆中。此后，下一个最佳实体是列表末尾的实体或堆中的最大实体中的较大者。这种设置的优点是，从链表中删除是一个恒定的时间操作，插入最大堆将是一个相对较小（相比于实体的总数）日志时间操作。

由于实体的值只会变得更糟，您可以懒惰地将它们从链接列表中删除 - 如果该项目毫无价值，则将其删除，如果其值已更改，则将其标记为“已更改”。检查链表末尾实体上的“changed”标志，如果它是“true”，则删除实体并将其添加到最大堆。惰性更新的优点是，您通常不需要更新堆中的项目（您只需更新链接列表中项目的值），并且如果项目发生更改，然后又变得毫无价值那么您可以将它从链接列表中删除，而无需将其添加到堆中。