Qu'est-ce qu'une structure de données de type bucket ou double bucket?

Question

Je suis en train de faire des lectures sur les implémentations d'algorithmes de chemins les plus courts et j'ai couru à plusieurs reprises que l'implémentation de l'algorithme de Dijkstra avec une structure de données Double Bucket est une bonne implémentation.

Cependant, je n'arrive pas à trouver ce que signifie réellement une implémentation à double seau, l'article de Wikipédia est plutôt vague. D'après ce que j'ai vu, il ressemble à une table/carte de hachage. Je n'ai jamais entendu parler de cela auparavant dans mes structures de données ou classes d'algorithmes.

Le document particulier, je lisais était ce,

Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Algorithmes de chemins les plus courts: Théorie et évaluation expérimentale. Programmation mathématique, 73 (2), 129-174.

Answer 1

Une structure de données de compartiment est une structure de données qui utilise les valeurs de clé comme indices des compartiments et stocke des postes de même valeur dans le compartiment correspondant. Naturellement, il est plus judicieux d'utiliser la structure de données du compartiment avec des valeurs de clé entière.

Supposons que B est une structure de données de compartiment telle que le compartiment B[x] stocke tous les éléments avec la valeur de clé x.

Utilisation du problème des chemins comme l'exemple Shortest, si vous avez 3 nœuds u, v et w dans l'ensemble Frontier, où les distances les plus courtes sont actuellement connues 3, 3 et 7, respectivement, puis B[3] = {u, v} et B[7] = {w}.

Analyse temporelle de la structure de données du godet qui est pertinente au problème des plus courts chemins:

• Insérer: O(1)
• Enlèvement: O(1)
• Diminution clé: O(1)
• Trouver minimum: O(c), où c est la valeur de clé maximale.

Ainsi, si l'algorithme de Dijkstra est mis en œuvre avec une structure de données de godet, vous avez O(m + nc) pour votre complexité totale, où m est le nombre d'arêtes et n est le nombre de nœuds.

---

Une structure de données à double godet, dans la plupart des cas, se réfère à la structure de données de godet où chaque godet contient une structure de données du godet.