AAL260 - ćw - temat B2
Kopce złączalne: dwumianowy i Fibonacciego.
Zadanie 30 "implementacja kopca
dwumianowego"
Zaimplementuj operacje Insert, ExtractMin oraz DecreaseKey na
kopcu dwumianowym.
Materiały: patrz slajdy z
wykładu.
Oczywiście niezbędna
będzie implementacja kluczowej operacji Union.
Jak wyglądają kopce dwumianowe? - dokonaj wizualizacji kopca dla małych
danych!
Zadanie 31 "kolejny algorytm
MST"
Zaimplementuj opisany niżej algorytm używając operacji na
kopcach dwumianowych ...
Dodatkowo oszacuj czas działania algorytmu.
Zadanie 32 "implementacja kopca Fibonacciego"
Zaimplementuj operacje Insert oraz ExtractMin na kopcu Fibonacciego.
Jak wyglądają kopce
Fibonacciego? - dokonaj wizualizacji kopca dla małych danych!
Zadanie 33 "kopiec dwumianowy vs
Fibonacciego"
Przeprowadź eksperyment pokazujący wyższość kolejki priorytetowej wykonanej z
kopca Fibonacciego nad wyknaną z kopca dwumianowego.
Jedyne operacje na jakie należy porównać to Insert i ExtractMin.
Zmierz fizyczny czas działania ciągu operacji Insert i ExtractMin
(k operacji Insert + k operacji ExtractMin)
dla kopca Fibonaciego i dla kopca dwumianowego,
dla tego samego ciągu danych wejsciowych;
powtórz ten eksperyment dla różnych danych wejściowych: losowych i
nielosowych.
Zadanie 34 "algorytm Prima: szybka
kolejka priorytetowa"
Wykonaj eksperyment pokazujący przewagę algorytmu Prima dla problemu MST,
gdy kolejka priorytetowa jest wykonana z kopca Fibonacciego
nad przypadkiem gdy jest wykonana z kopca dwumianowego.
Uwaga: tu będzie potrzebna
operacja DecreaseKey dla kopca Fibonacciego.
Zastanów się dokładnie dla jakich grafów ta przewaga ma prawo się
pojawić
(spojrz na oszacowanie czasu działania w obu przypadkach).
Uwaga 2 !!!: chodzi tu o tradycyjny alg Prima, a nie ten z zadania 31 !!!