algorithm - 什么是桶或双桶数据结构？

Question

我正在阅读有关最短路径算法实现的一些资料，并且反复发现使用双桶数据结构实现 Dijkstra 算法是一个很好的实现。

但是我似乎无法找到双桶实现的实际含义，关于它的维基百科文章有点含糊。据我所见，它类似于哈希表/映射。我以前在我的数据结构或算法类中从未听说过这个。

我正在阅读的特定论文是这样的，

Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996)。最短路径算法:理论和实验评估。数学规划,73(2), 129-174.

Answer 1

桶数据结构是一种以键值作为桶索引的数据结构，将具有相同键值的项存储在对应的桶中。自然地，使用具有整数键值的桶数据结构是最有意义的。

假设 B是一个 bucket 数据结构，使得 bucket B[x]存储键值为 x 的所有项目.

以最短路径问题为例，如果你有3个节点u , v和 w在 Frontier 集合中，当前已知的最短距离分别为 3、3 和 7，则 B[3] = {u, v}和 B[7] = {w} .

与最短路径问题相关的桶数据结构的时间分析:

• 插入:O(1)
• 移除:O(1)
• 减少键:O(1)
• 找到最小值:O(c) , 其中c是最大键值。

因此，如果 Dijkstra 的算法是用桶数据结构实现的，你有 O(m + nc)对于您的总时间复杂度，其中 m是边数，n是节点数。

---

双桶数据结构，在大多数情况下，是指每个桶包含一个桶数据结构的桶数据结构。