Zadanie 1

$d$-kopcem typu MIN, $d \ge 2$, nazywamy zupełne drzewo $d$-arne z kluczami rozmieszczonymi w porządku kopcowym typu MIN.

Zadanie 2

Drzewem lewicowym nazywamy drzewo binarne, w którym dla każdego wierzchołka długość skrajnie prawej ścieżki w jego lewym poddrzewie jest nie mniejsza od długości skrajnie prawej ścieżki w jego prawym poddrzewie. Kopcem lewicowym typu MIN nazywamy drzewo lewicowe z kluczami rozmieszczonym w porządku kopcowym typu MIN.
Zaproponuj efektywne implementacje operacji kolejki priorytetowej (Build, Min, DeleteMin, DecraseKey) z użyciem kopców lewicowych.

Zadanie 3

Dana jest rodzina $n$ niepustych podzbiorów zbioru $\{1, 2, \ldots, n \}$, z których każdy to całkowitoliczbowy przedział postaci $[i,j]$, $i \le j$. Zaprojektuj efektywny algorytm sprawdzania, czy zadana rodzina posiada system różnych reprezentantów, a jeśli tak, to podaje jeden z nich.

Zadanie 4

W algorytmie Dijkstry ciąg wartości otrzymywanych w wyniku wywołań funkcji Min jest niemalejący. Wykorzystaj ten fakt i zaproponuj implementację implementację algorytmu Dijkstry w czasie $O(m + kn)$, gdy wagi krawędzi są liczbami całkowitym z przedziału $[1..k ]$.

Zadanie 5: rozgłaszanie w drzewie

Dane jest drzewo z wyróżnionym wierzchołkiem $s$ - źródłem rozgłaszania.