ASD Ćwiczenia 9

ZadanieUdowodnij Lemat 1. RozwiązanieIndukcja po $k$. ZadanieDo początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000.Czy teraz w jej skład wchodzi drzewo $B_5$? RozwiązanieTak, bo $1000=2^9+2^8+2^7+2^6+{\mathbf{𝟐}}^{\mathbf{𝟓}}+2^3$. ZadanieNarysuj (a) kolejkę dwumianową (b) kopiec Fibonacciego otrzymane w wyniku wstawienia do początkowo pustej struktury kolejno kluczy 3, 1, 4, 15, 9, 2, 6, wykonaniu Delmin, zmniejszeniu klucza 15 do wartości 5 i usunięciu klucza 4. Rozwiązanie********** rysunek *************** ZadanieZaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwiarealizację wszystkich operacji z podanymi kosztami. RozwiązanieKolejka dwumianowa:W każdym węźle pola: klucz, ojciec, lewy syn, prawy brat;wskaźniki do brata w korzeniach wykorzystywane do utrzymywania listy drzew; listy braci (i korzeni) cykliczne. Kopiec Fibonacciego:Podobnie, ale listy braci dwukierunkowe oraz dodatkowe pole z flagą logiczną, mówiącą czy węzeł stracił syna od czasu ostatniego odcięcia. Dostęp do listy drzew przez wskaźnik do korzenia z najmniejszym kluczem. ZadanieNapisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych. RozwiązanieZobacz [CLRS], podrozdz. 19.2 (konieczne są drobne modyfikacje). Zadanie Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji nakopcach Fibonacciego? Rozwiązanie MakePQ: 1 Insert: 1 FindMin: 1 DelMin n DecreaseKey n Delete n Meld 1 ZadanieNapisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego. RozwiązanieZobacz [CLRS], podrozdz. 20.2 i 20.3. ZadanieCzy wysokość drzewa w $n$-wierzchołkowym kopcu Fibonacciego jest $O(\lg n)$? RozwiązanieNie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii. ZadanieCzy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany $o(\log n)$? RozwiązanieNie, bo wtedy można by użyc takiej struktury danych do posortowania $n$ elementów w czasie $o(n\log n)$.