algorithm - 按最大值和 ID 检索的最佳数据结构？

Question

我有相当多的固定大小的记录。每条记录都有很多字段，ID和Value就在其中。我想知道哪种数据结构最好，这样我就可以

1. 通过 ID(唯一)非常快速地定位记录，

2. 列出具有最大值的 100 条记录。

最大堆似乎可行，但远非完美；您有更智能的解决方案吗？

谢谢。

Answer 1

混合数据结构很可能是最好的。为了通过 ID 进行高效查找，一个好的结构显然是一个哈希表。为了支持前 100 次迭代，最大堆或二叉树是一个很好的选择。插入和删除时，您只需对两个结构进行操作。如果迭代案例的 100 是固定的，那么迭代经常发生并且插入/删除不会严重偏向前 100 个，只需将前 100 个保持为排序数组并溢出到最大堆。这不会修改结构的大 O 复杂性，但会为迭代情况提供非常好的常数因子加速。