algorithm - 排序数据结构 : random in, 最低出

Question

我需要一个数据结构，支持键值对的插入，以及具有最低键的对的提取。插入和提取可以随时发生，因此数据结构必须保持连续排序，提取包括从列表中删除对。此外，插入的新对的键值不能低于最近提取的对的键值。插入的键对的值也会随着时间的推移而增加。

要求:

• key :64 位无符号整数
• 一次列出的最大条目数:~10^6
• 每秒插入(和提取)的条目:~10^5
• 提取时有效删除条目
• 插入的键对:当前最低键 > 键 > 当前最低键 + 10^7
• 内存要求无关紧要，计算复杂度也无关
• 一些对可以有相同的 key

Answer 1

正如其他人所建议的那样，二叉堆是一个很好的选择。我发现它们在大多数情况下都表现得很好。 d-ary heap (d 为 3 或 4)，可以让您获得 10% 的性能提升，而增加的实现复杂性却很少。在我对您所说大小的堆进行的实验中，3 元堆明显快于二进制(2 元)堆。

另一个选项是 skip list ，这会给你 O(log n) 插入和 O(1) 删除最低。实现跳跃列表比二叉堆稍微复杂一些，它需要更多的内存，并且常数因子更高。插入可能会比在堆中稍慢，但移除会快得多。它是否足够快以弥补额外的内存成本和增加的实现复杂性是您必须自己回答的问题。