什麼是桶或雙桶數據結構？

Question

我正在做一些關於最短路徑算法實現的閱讀，並且已經反覆運行，實現具有Double-Bucket數據結構的Dijkstra算法是一個很好的實現。

但是，我似乎無法找到雙桶實現的實際含義，維基百科上的文章有點含糊。從我看到的它類似於散列表/地圖。在我的數據結構或算法類中，我從來沒有聽說過這個。

的特定紙張我正在讀是這樣的，

Cherkassky，B. V.，拔，A. V.，& Radzik，T。（1996）。最短路徑算法：理論和實驗評估。數學規劃，73（2），129-174。

Answer 1

桶數據結構是一種數據結構，它使用鍵值作爲桶的索引，並將相同鍵值的項存儲在相應的桶中。當然，使用具有整數鍵值的桶數據結構是最有意義的。

假設B是一個存儲桶數據結構，使得存儲桶B[x]存儲了所有關鍵值爲x的項目。

使用最短路徑問題，因爲例如，如果有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是節點的數量。

---

雙桶數據結構，大多數情況下是指桶數據結構，其中每個桶包含一個桶數據結構。