从桶排序中检索排序列表的有效方法？

Question

当桶排序中键的分布稀疏时，可能会出现很多空桶。 我们如何有效地检索排序后的列表（即实现串联操作）？

我们想要实现一个基于桶的优先级队列，但是搜索第一个非空桶可能需要很多时间。所以我们想知道一种更聪明的方法来做到这一点。

例如，如果我们得到一个包含数百万个10、1000、50000、100000、6400000、10000000等的列表，我们如何使用桶排序检索排序后的列表？

另一个更难的例子是，1, 100, 101, ..., 999, 1000, 100000, 100001, ... 999999, 1000000, 100000000, 100000001, ..., 199999999。

可能存在更困难的情况，即某些段内的分布很密集，但段之间可能存在巨大的差距。

Answer 1

您的申请必须很特别。 如果存储桶稀疏，人们可能会认为每个存储桶平均只有一两个项目。 如果是这样，那么桶排序对你没有任何好处——只需将项目放入堆中即可。

如果桶并不是真的那么稀疏，即如果桶的数量是 <= a few times the number of items, then the bucket sort suffices -- iterate through the buckets in order and the cost will be O(N) in the number of items.

如果每个非空存储桶有很多项目，并且每个项目有很多存储桶，那么您可能想解释一下您的用例，但是当我过去看到这一点时，将每个存储桶插入到堆中是合理的。变为非空。

Answer 2

您的问题的简单答案是“没有额外的数据结构来跟踪哪些存储桶有项目。”

有多种方法可以进行桶排序。 “最佳”在很大程度上取决于键的范围、项目的数量以及unique项目的数量。如果您的范围是 0 到 1,000,000 并且您知道您将拥有 50% 的唯一性，那么包含 1,000,000 个存储桶的单个数组很容易使用，您不会浪费太多空间，也不会浪费很多时间跳过空桶。

但是，如果您谈论的是人口稀少的数亿范围，那么您最终会浪费大量内存和大量时间来跳过空桶。在极端情况下，您甚至无法分配足够大的数组来覆盖整个范围。

实现桶排序的另一种常见方法是使用字典或哈希图。这个想法是：

initialize empty hash map
for each item in list
    if key already in hash map
        add item to that bucket
    else
        create new bucket in hash map

当然，完成填充后，您必须按键对存储桶进行排序，但是对几千个（如果是的话）存储桶进行排序需要很短的时间。而且您最终不会在空存储桶上浪费千兆字节的内存。

当我构建基于桶的优先级队列时，我使用了字典方法。我维护了一个按索引键控的字典，并将每个项目添加到正确的存储桶中。我还维护了一个简单的存储桶二进制堆。所以向堆中添加一个项目就变成了：

if item.key exists in dictionary
    dictionary[item.key].add(item)  // adds item to bucket
else
{
    dictionary.add(item.key, item) // creates a new bucket
    heap.push(dictionary[item.key]) // pushes the bucket onto the heap
}

从堆中删除一个项目变成：

bucket = heap.peek()
item = bucket.getFirst()
if (bucket.count() == 0)
{
    // bucket is empty. Remove from heap and from dictionary
    heap.pop()
    dictionary.remove(item.key)
}
return item

这表现得相当不错。因为我的钥匙很少，而且桶装得很满，所以堆本身很少有任何活动。大多数活动涉及向堆中已有的存储桶添加内容或从存储桶中删除内容。堆得到锻炼的唯一时间是当一个桶被清空时，或者当我添加一个新桶时。所以平均而言，插入和删除都非常接近 O(1)。

这对我来说效果很好，因为我的密钥范围非常大（10 个字符的字母数字），单个项目的数量有数亿或数十亿，但任何时候使用的唯一密钥的数量有数千个。字典间接寻址会产生一些轻微的开销，但这完全可以被处理几千个而不是数亿个项目所节省的费用所抵消。