什么是桶还是双桶数据结构？

Question

我正在读一些关于最短路径算法实现的文章，并且一遍又一遍地发现，用双桶数据结构实现Dijkstra算法是一个很好的实现。

然而，我似乎找不到双桶实现的真正含义，维基百科上的文章有点含糊不清。据我所见，它类似于哈希表/映射。在我的数据结构或算法类中，我从未听说过这种情况。

我读的特别报纸是这样的，

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

Answer 1

桶数据结构是一种数据结构，它使用键值作为桶的索引，并将相同键值的项存储在相应的桶中。当然，使用带整数键值的桶数据结构是最有意义的。

假设B是一个存储桶数据结构，以便存储所有具有x键值的项。

以最短路径问题为例，如果在Frontier集中有3个节点u、v和w，其中当前已知的最短距离分别为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是节点数。

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