10
Czy dla Haskella dostępna jest stertka/kolejka priorytetowa Fibonacciego? (? Albo nawet asymptotycznie lepszy) Znalazłem listę różnych implementacjach priorytet kolejki w this question, ale nie mogę znaleźć, jeśli każdy z nich spełnia zamortyzowanego czas pracy pryzmach Fibonacciego:Czy istnieje kolejka priorytetowa Fibonacciego dla Haskella?
- Find-minimum to O (1) zamortyzowany czas.
- Operacja wstawiania, zmniejszania klucza i scalania (zrostu) to O (1) amortyzowany czas.
- Operacje usunięcia i usunięcia minimum to O (log n) zamortyzowany czas.
Zobacz the comparison of theoretic bounds.
Jest możliwe, że nie istnieje kod produkcyjny, ponieważ stałe czynniki generalnie powodują, że stosy Fibonacciego wolniej niż dwumianowe hałdy dla rozsądnych rozmiarów zestawów danych, pomimo teoretycznej przewagi asymptotycznej. –
@OliCharlesworth Ciekawe, czy mógłbyś podać przybliżoną skalę rozmiarów stosów Fibonacciego? –
TBH, to jest trochę poza moim obszarem; Przeczytałem tylko o takich wadach (zobacz np. [CLRS] (http://en.wikipedia.org/wiki/CLRS)). Nie cytuj mnie na ten temat;) –