Algorytmy i Struktury Danych

9. Kopce

1. (1p.) Niech x – węzeł w drzewie dwumianowym kopca dwumianowego

taki, że sibling[x] 6= N IL. Jaka jest zależność między degree[sibling[x]] a
degree

[x] w przypadkach gdy x nie jest korzeniem i gdy jest korzeniem?

2. (1p.) Jeżeli x jest węzłem różnym od korzenia w drzewie dwumiano-

wym kopca dwumianowego, to jaka jest zależność między degree[p[x]] a
degree

[x]?

3. (2p.) Załóżmy, że węzły drzewa dwumianowego B

k

są ponumerowane w

porządku postorder (t.j. nadajemy kolejne numery w porządku postorder
węzłom w poddrzewach korzenia od lewej do prawej, a następnie numeru-
jemy korzeń). Pokaż, że binarna reprezentacja numeru węzła x o głębo-
kości i ma k − i jedynek. Pokaż, że stopień x jest równy liczbie jedynek
na prawo od skrajnie prawego zera, w binarnej reprezentacji numeru x.

4. (2p.) Podaj przykład dwóch n-elementowych kopców binarnych, których

scalenie za pomocą procedury Build-Heap wymaga czasu Θ(n).

5. (1p.) Napisz pseudokod dla procedury Binomial-Heap-Merge.

6. (1p.) Wyjaśnij dlaczego Binomial-Heap-Minimum mogłaby nie działać

poprawnie, gdyby klucze mogły przyjmować wartość ∞. Popraw jej kod,
tak aby działała poprawnie i w takim przypadku.

7. (1p.) Przypuśćmy, że nie mamy możliwości reprezentacji −∞. Napisz

kod Binomial-Heap-Delete, tak aby działała porawnie w takiej sytuacji.
Czas działania ma być nadal O(lg n).

8. (2p.) Uzasadnij, że jeśli jedynymi operacjami na kluczach są porówna-

nia między dwoma kluczami, to nie wszystkie operacje kopca złączalnego
mogą działać w zamortyzowanym czasie O(1).

9. (2p.) Czy prawdą jest, że wysokość n-węzłowego kopca Fibonacciego wy-

nosi O(lg n)?

10. (2p.) W kopcu Fibonacciego następuje odcinanie kaskadowe węzła x po

utracie drugiego syna. Gdybyśmy odcinali węzeł po utracie k-tego syna,
to dla jakich k będzie zachodzić D(n) = O(lg n)? (D(n) – maksymalny
stopień węzła w n-elementowym kopcu Fibonacciego.)

1