Pseudocode pour la file d'attente Brodal

12

J'essaie de trouver plus de ressources concernant le tas Brodal . Tout ce que j'ai trouvé est une implémentation haskell du tas Brodal-Okasaki , mais je pense que ce sont des tas asymétriques , est-ce correct? De plus, je suis analphabète à Haskell, ce qui n'aide pas beaucoup. Quelqu'un a-t-il (ou connaît-il) une implémentation de file d'attente Brodal en pseudocode, C, C ++, Python?

Veuillez également corriger si mes hypothèses ci-dessus sont fausses.

research data-structures Kimvais
la source
3
Cherchez-vous à implémenter spécifiquement la file d'attente Brodal, ou recherchez-vous une implémentation efficace d'une file d'attente prioritaire? Brodal a mentionné dans la conclusion de son article qu'ils ne sont pas pratiques sans quelques recherches supplémentaires dans le domaine. Son article a été abondamment cité, peut-être quelque chose d'utile? Le CLR Introduction to Algorithms a une section sur les files d'attente prioritaires, mais il fait référence à un travail beaucoup plus ancien dans les files d'attente prioritaires.
Jay Elston
2
La file d'attente Brodal d'origine utilise une affectation destructive, donc la version Haskell doit avoir quelques modifications.
Fred Foo

Réponses:

2

L'implémentation Haskell est basée sur le tas fonctionnel Brodal-Okasaki et vous avez raison, c'est une variation de tas asymétriques. Le document est rédigé très clairement, ce serait donc une bonne ressource.

Concernant l'implémentation, il existe également une implémentation dans Scala dans le cadre de la bibliothèque scalaz.

maayank
la source
1

Ceci est une réponse partielle car je n'ai pas encore compris comment traduire le code en quelque chose qui n'est pas Haskell. La raison pour laquelle je peux dire pour eux d'avoir à utiliser Haskell est que Haskell est paresseux. Le tas Brodal-Okasaki doit être implémenté de façon paresseuse dans le papier. Donc, ce dont vous avez besoin est un moyen de fournir cette fonctionnalité à une autre langue ainsi que toutes les autres exigences (telles que les structures de données purement fonctionnelles) dont le tas BO pourrait avoir besoin.

Ingénieur du monde
la source