Witam
Powoli zaczynam się uczyć na egzamin z AiSD, dotarłem do kopca dwumianowego. Do tej pory znałem zastosowanie większości struktur danych ale przy kopcu dwumianowym nie mam pomysłu do czego się to może przydać. Ktoś może wie ?
0
0
Większość operacji na kopcu dwumianowym ma złożoność O(logN), co więcej, złożoność dla wyszukania elementu najmniejszego to O(1). Oprócz standardowych operacji typu insert/delete/find jest jeszcze kilka innych pozwalających na implementację kolejek priorytetowych.
Jeśli chodzi o konkrety, to dzięki kopcowi można poprawić złożoność algorytmu Dijsktry do O(NlogN). We wspomnianym algorytmie kolejka priorytetowa wykorzystywana jest przy relaksacji krawędzi. To wszystko dzięki operacji Find_Minimum realizowanej przy złożoności O(1).
pzdr,