ASD Ćwiczenia 9

Ćwiczenie [Dowód lematu 1]

Udowodnij lemat 1

Rozwiązanie

Indukcja po $k$.

Ćwiczenie [Kolejka dwumianowa 1]

Do początkowo pustej kolejki dwumianowej wstawiamy klucze 1, 2, ..., 1000. Czy teraz w jej skład wchodzi drzewo $B_5$?

Rozwiązanie

Tak, bo $1000=2^9+2^8+2^7+2^6+{\mathbf{𝟐}}^{\mathbf{𝟓}}+2^3$.

Ćwiczenie [Kolejka dwumianowa 2]

Narysuj (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

Ćwiczenie [Kolejka dwumianowa 3]

Zaproponuj reprezentację komputerową kolejki dwumianowej i kopca Fibonacciego, która umożliwia realizację wszystkich operacji z podanymi kosztami.

Rozwiązanie

Kolejka 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.

Ćwiczenie [Meld i DelMin]

Napisz pseudokod operacji Meld i DelMin na kolejkach dwumianowych.

Rozwiązanie

Zobacz [CLRS], podrozdz. 19.2 (konieczne są drobne modyfikacje).

Ćwiczenie [Koszty operacji]

Jakie są pesymistyczne (nie zamortyzowane) koszty poszczególnych operacji na kopcach Fibonacciego?

Rozwiązanie

MakePQ: 1

Insert: 1

FindMin: 1

DelMin n

DecreaseKey n

Delete n

Meld 1

Ćwiczenie [Pseudokod]

Napisz pseudokod operacji DelMin i DecreaseKey na kopcach Fibonacciego.

Rozwiązanie

Zobacz [CLRS], podrozdz. 20.2 i 20.3.

Ćwiczenie [Wysokość drzewa]

Czy wysokość drzewa w $n$-wierzchołkowym kopcu Fibonacciego jest $O(\lg n)$?

Rozwiązanie

Nie. Nietrudno podać przykład ciągu operacji, który prowadzi do powstania drzewa-linii.

Ćwiczenie [Modyfikacja kopca Fibonacciego]

Czy możliwa jest taka modyfikacja kopca Fibonacciego, żeby zarówno operacja Insert, jak i DelMin miały koszt zamortyzowany $o(\log n)$?

Rozwiązanie

Nie, bo wtedy można by użyc takiej struktury danych do posortowania $n$ elementów w czasie $o(n\log n)$.