Hej,
Zaimplementowałem 3 kopce by porównać czasy ich działania na moim komputerze a przy okazji sprawdzenie na ile teoretyczna złożoność czasowa zgadza się z praktyką, i tu pojawia się problem.
Kopiec dwumianowy działa zdecydowanie wolniej od pozostałych, o ile przy niewielkich dych nie odstaje zbyt wiele od reszty, o tyle np przy 200 mb danych wejściowych, 20 000 wierzchołków, 10 000 000 połączeń, sytuacja przedstawia się tak:
Przy Dijkstrze:
Kopiec | Czas
Binarny | 0,782176s
Fibonacci | 1,020952s
Dwumianowy | 12,581656s
Usuwanie największej wartości z kopca wygląda tak:
Kopiec | Czas
Binarny | 0,011849s
Fibonacci | 0,048943s
Dwumianowy | 5,858372s
Pytanie jest następujące, czy takie rozbieżności są dopuszczalne, czy jest to efekt błędu w implementacji?