algorithm - 排序数据结构：随机入，最低出

Question

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

要求：

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

Answer 1

正如其他人所建议的那样，二叉堆是一个很好的选择。我发现它们在大多数情况下都表现得很好。一个d堆（d为 3 或 4）可以使您的性能提高 10%，而几乎不增加实现复杂性。在我对您所说的大小的堆进行的实验中，3 元堆明显比二进制（2 元）堆快。

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

Answer 2

你所描述的听起来很像一个优先级队列，优先级由键比较确定。

理想的实现是二叉堆，因为这会导致O(log n)插入和删除，总体上比一个存在O(1)和另一个存在更好O(n)。如果您希望插入或删除很少，您可以在实现中使用排序或未排序的序列，但我仍然会犹豫是否这样做。

至于插入元素的键大于最后一个移除的元素的要求，这将只需要一个额外的成员变量来指示最后一个移除的键的值；每次删除时都更新它。这样做不会影响渐近运行时间。或者，您可以在代码中包含一个变量，在调用插入方法之前检查插入候选者。无论哪种方式，您都需要存储最后一个删除元素的键，并在调用 insert 方法之前将其与要插入的元素进行比较。

Answer 3

一种选择是优先队列，它满足您的要求——随机输入，最低输出，它执行O(logn)插入和删除（弹出）。