Pseudokod dla kolejki Brodal

12

Próbuję znaleźć więcej zasobów dotyczących sterty Brodal . Wszystko, co znalazłem, to implementacja haskellowa stosu Brodal-Okasaki , ale myślę , że są to stosy skośne , prawda? Ponadto jestem niepiśmienny w Haskell, więc to niewiele pomaga. Czy ktoś ma (lub wie) o implementacji kolejki Brodal w pseudokodzie, C, C ++, Python?

Proszę również poprawić, jeśli moje powyższe założenia są błędne.

research data-structures Kimvais
źródło
3
Czy chcesz konkretnie wdrożyć kolejkę Brodal, czy szukasz wydajnej implementacji kolejki priorytetowej? Brodal wspomniał na zakończenie swojej pracy, że nie są one praktyczne bez dalszych badań w tej dziedzinie. Jego artykuł był szeroko cytowany, może coś przydatnego? Wprowadzenie do algorytmów CLR zawiera sekcję dotyczącą kolejek priorytetowych, ale odwołuje się do znacznie wcześniejszej pracy w kolejkach priorytetowych.
Jay Elston,
2
Oryginalna kolejka Brodal wykorzystuje destrukcyjne przypisanie, więc wersja Haskell musi mieć pewne modyfikacje.
Fred Foo,

Odpowiedzi:

2

Implementacja Haskell oparta jest na funkcjonalnej hałdzie Brodal-Okasaki i masz rację, jest to odmiana stosów skośnych. Artykuł jest napisany bardzo wyraźnie, więc byłby to dobry zasób.

Jeśli chodzi o implementację, istnieje również implementacja w Scali jako część biblioteki scalaz.

maayank
źródło
1

To częściowa odpowiedź, ponieważ jeszcze nie wymyśliłem, jak przetłumaczyć kod na coś, co nie jest Haskell. O ile mogę powiedzieć, że muszą używać Haskell, to, że Haskell jest leniwy. Stos papieru Brodal-Okasaki należy wszczepić w gazecie w leniwy sposób. Potrzebny jest więc sposób zapewnienia tej funkcjonalności innemu językowi wraz z wszelkimi innymi wymaganiami (takimi jak czysto funkcjonalne struktury danych), których może potrzebować Kupa BO.

Inżynier świata
źródło