algorithm - 具有快速随机访问的类堆数据结构？

Question

我的情况是这样的:

• 我有一个实体集合，每个实体都有一个“goodness”属性。
• 我希望一次抓取一个实体，从“最好”到“最差”。
• 在抓取一个“最佳”实体后，我的其他几个(相对较少)实体的“善良”属性发生变化，并且必须将此更改纳入我即将抓取的下一个“最佳”实体的决定中。
• 一些(相对较少的)实体在抓取后可能会变得“毫无值(value)”，这些应该从我的收藏中移除。
• 鉴于我刚刚抓取的实体，我很容易构建一组现在“脏”的对象，也就是说，一组可能具有现在不同的“善”或已经成为“毫无值(value)。”

所以，我需要一个数据结构，允许我:

• 快速获取集合中“最大的”(如最大堆)。
• 快速更新我集合中对象的基本排序以适应上述情况。 (在堆中很容易做到，如果我们可以在底层堆实现中访问脏对象的位置，例如数组索引。)
• 可以保证我收藏的条目之间没有冲突。 (这些条目是对我上面描述的实体的引用。)

我的想法是将最大堆与无序映射一起使用，以堆条目为键，并且其值等于，例如，对象在堆实现中的底层数组中的相应索引。

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

Answer 1

如果在抓取最佳实体时几乎没有成员受到影响，那么您可以通过使用链表和无序映射(每个都包含原始实体集)和最大堆来改进运行时间。从链接列表的末尾删除最佳实体后，您将使用 map 定位受影响的实体，将它们从列表中删除并将无值(value)的实体添加到最大堆。此后，下一个最佳实体是列表末尾的实体或堆中的最大实体中的较大者。这种设置的优点是从链表中移除是一个常量时间操作，而插入到最大堆中将是一个相对较小(与实体总数相比)的日志时间操作。

因为实体的值只会变得更糟，您可以懒惰地将它们从链表中删除 - 如果该项目没有值(value)，则将其删除，如果其值已更改，则将其标记为“已更改”。检查链接列表末尾实体上的“已更改”标志，如果为“真”，则删除该实体并将其添加到最大堆。惰性更新的优点是你通常不需要更新堆中的项目(你只需要更新链接列表中项目的值)，如果一个项目被更改然后变得毫无值(value)然后你可以从链表中删除它，而不必将它添加到堆中。